我有两段代码,并解释了它们属于哪个大O类。然而,尽管我可能会尝试,我无法将解释与通过查看或执行样本运行得到的结果进行比较。
第一个:

long count = 0;
long n = 1000;
long i, j, k;
    for(i = 0; i < n; i++)
        for (j = 0; j < i * i; j++)
            for (k = 0; k < j; k++)
                count++;

这方面的样本一直给我n^4,但我得到的答案是“j可以和i^2一样大,也可以和n^2一样大。k可以和j一样大,也就是n^2。因此,运行时间与N^N^2^N^2成正比,即O(N^5)
第二个片段:
long i, j, k;
long n = 1000;
long count = 0;
for (i = 1; i < n; i++)
    for (j = 1; j < i * i; j++)
        if (j % i == 0)
            for (k = 0; k < j; k++)
                count++;

对于这一点,注释说“if语句最多执行n3次,由前面的参数执行,但它只有o(n^2)次是真的(因为它对每个i都是真的i次)。因此,最里面的循环只执行o(n^2)次。每次通过,需要O(j^2)=O(N^2)时间,总共O(N^4)
对此,音符对于n^4来说似乎足够精确(尽管我一直得到n^4/10的结果)。我不遵循模的计算,只为每一个i的真i次,然而,它似乎进入那个循环少得多。
所以问题是有谁能澄清我不理解的东西吗?

最佳答案

对于第一个:

sum from i = 0 to n-1 of
    sum from j = 0 to i*i-1 of
        sum from k = 0 to j-1 of
            1

我们知道1m次之和等于m,所以我们可以将其减少到
sum from i = 0 to n-1 of
    sum from j = 0 to i*i-1 of
        j

我们知道总和,所以我们可以进一步减少:
sum from i = 1 to n-1 of
    (i * i - 1) * i * i / 2 = (1/2) * (i * i * i * i - i * i)

我们可以通过将1 + 2 + ... + m = m * (m + 1) / 2排除在求和项之外,然后将(1/2)i * i * i * i项分开来简化这个过程;但是,求和比单独使用i * i项更难,也不太为人所知。结果确实是i因此Theta(n^5);为了至少直观地理解为什么会出现这种情况,请认识到差异O(n^5)的顺序是f(n+1) - f(n) = (1/2)(n^4-n^2),因此如果n^4是一个连续函数,而这个差异是导数,那么f的顺序将更高。
对于第二种情况:
sum from i = 0 to n-1 of
    sum from j = 0 to i-1 of
        sum from k = 0 to i*j-1
            1

注意,f现在只为最里面的循环设置不同的值:j内部循环的迭代次数是i的计数器值的1倍。我们做这个乘法移位以避免引入“步”符号,这样我们就可以使用通常的数学结果。
sum from i = 0 to n-1 of
    sum from j = 0 to i-1 of
        i*j

sum from i = 0 to n-1 of
    i * (1/2) * i * (i - 1) = (1/2)(i * i * i - i)

同样,我们可以作弊或做数学运算,或者我们可以再次利用我们的直觉(正确地)推测结果是0, i, 2i, ..., (i-1)i

关于algorithm - 两个代码片段的大O表示法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/46410975/

10-11 22:07
查看更多