我有两段代码,并解释了它们属于哪个大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
我们知道1
m
次之和等于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/