我已经做了一些运行时复杂性近似练习已经有一段时间了,我一直试图围绕以下在线发现的例子(评论是我自己的):
例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
。