algorithm - 计算大 O 表示法:2 个嵌套循环的 O(n^4) 和没有递归的 O(log n)
问题描述
自从我做了一些运行时复杂度近似练习以来已经有一段时间了,我一直在尝试围绕以下在线找到的示例(评论是我自己的):
示例 1:
for ( int i = 1 ; i <= n ; i++) { //n
for ( int j = 1; j <= i*i ; j++) { // 1+2^2+3^2+...+n^2
if ( j % i == 0) {
for ( int k = 0 ; k < j ; k++ ){ // 1+2^2+3^2+...+n^2
sum++;
}
}
}
}
解决方案表说它是 O(n^4),但我看不到它。我确定我错过了一些东西,因为在我的评论中我计算出在最坏的情况下它是 O(n^5)。
示例 2:
i = 1 ;
L2 = -1;
while ( i <= n ) {
i = i*2 ; // 2 + 2^2 + 2^3+ ...+ 2^n
L2++;
}
提到的解决方案是 O(log n)。我认为在最坏的情况下,我会得到 2^n <= n 的结果,因此 n <= log n。在这里应用上界函数的典型定义更直观(即 f(n) <= O(g(x)) )
我基本上想知道我错过了什么,以及我应该经历哪些步骤/指南来为这两种情况(尤其是第一个示例)找到正确的大 O 复杂性。对于任何不清楚的细节,我深表歉意,我很乐意添加更多说明。在此先感谢,我感谢任何见解!
解决方案
示例 1 是O(n^5)
因为 big-O 是一个上限。也是Theta(n^4)
因为 if 语句让最里面的循环每次i
迭代都只运行一次,所以运行时间是Theta(n sum_{i=1}^n (i*i * 1/i * i*i)) = Theta(n^4)
.
示例 2 是O(log n)
. 在第j
th 次迭代中,i
是2^j
,并且阈值2^j > n
是j > lg n
。