java - 作为运行时间 N 的函数的增长顺序

Question

我正在尝试练习算法的复杂性，我该怎么做？！我不明白这个问题或我必须做些什么计算才能得到它......任何帮助都会很棒！

int N = 50 ;
int sum = 0 ;
for (int n = N ; n > 0 ; n/=2 ) {
    for (int i = 0 ; i < n ; i++) {
        sum++ ;
    } 
}

标签： javaalgorithmtime-complexitybig-o

Answer 1

您可以在外部循环的每次迭代中根据内部循环编写迭代N次数，例如：

T(N) = N + N/2 + N/4 + ... + 1 = N (1 + 1/2 + 1/4 + ...+ 1/(2^log(N)) = Theta(N)

因此，时间复杂度O(N)也在其中。