为什么这个算法是O(nlogn)？
Why is this algorithm O(nlogn)?
我正在看一本关于算法分析的书，发现了一个我不知道如何获得时间复杂度的算法，尽管书上说它是O(nlogn)。
算法如下：
sum1=0;
for(k=1; k<=n; k*=2)
for(j=1; j<=n; j++)
sum1++;
也许让自己相信 O(n*lgn) 运行 宁时间的最简单方法是 运行 在 sheet 纸上写算法。考虑当 n 为 64 时会发生什么。那么外层循环变量 k 将采用以下值：
1 2 4 8 16 32 64
log_2(64)就是6，就是上面的项数加一。您可以继续这一推理得出外循环将花费 O(lgn) 运行ning 时间的结论。
完全独立于外循环的内循环是O(n)。将这两项相乘得到 O(lgn*n).
在您的第一个循环 for(k=1; k<=n; k*=2) 中，变量 k 在 log n 步中达到 n 的值，因为您在每个步骤中将值加倍。
第二个循环 for(j=1; j<=n; j++) 只是一个线性循环，因此需要 n 步。
因此，总时间为 O(nlogn)，因为循环是嵌套的。
添加一点数学细节...
设a为外循环for(k=1; k<=n; k*=2)运行的次数。然后这个循环将 运行 2^a 次（注意循环增量 k*=2 ）。所以我们有 n = 2^a。两边取基数 2 对数求解 a，则得到 a = log_2(n)
自从内循环运行秒n次，一共是O(nlog_2(n)).
补充一下@qwerty的回答，如果a是外循环的次数运行s:
k 取值 1, 2, 4, ..., 2^a 和 2^a <= n
两边取log：log_2(2^a) <= log_2(n)，即a <= log_2(n)
所以外层循环的上限是log_2(n)，即它不能运行超过log_2(n)次。
我正在看一本关于算法分析的书，发现了一个我不知道如何获得时间复杂度的算法，尽管书上说它是O(nlogn)。
算法如下：
sum1=0;
for(k=1; k<=n; k*=2)
for(j=1; j<=n; j++)
sum1++;
也许让自己相信 O(n*lgn) 运行 宁时间的最简单方法是 运行 在 sheet 纸上写算法。考虑当 n 为 64 时会发生什么。那么外层循环变量 k 将采用以下值：
1 2 4 8 16 32 64
log_2(64)就是6，就是上面的项数加一。您可以继续这一推理得出外循环将花费 O(lgn) 运行ning 时间的结论。
完全独立于外循环的内循环是O(n)。将这两项相乘得到 O(lgn*n).
在您的第一个循环 for(k=1; k<=n; k*=2) 中，变量 k 在 log n 步中达到 n 的值，因为您在每个步骤中将值加倍。
第二个循环 for(j=1; j<=n; j++) 只是一个线性循环，因此需要 n 步。
因此，总时间为 O(nlogn)，因为循环是嵌套的。
添加一点数学细节...
设a为外循环for(k=1; k<=n; k*=2)运行的次数。然后这个循环将 运行 2^a 次（注意循环增量 k*=2 ）。所以我们有 n = 2^a。两边取基数 2 对数求解 a，则得到 a = log_2(n)
自从内循环运行秒n次，一共是O(nlog_2(n)).
补充一下@qwerty的回答，如果a是外循环的次数运行s:
k 取值 1, 2, 4, ..., 2^a 和 2^a <= n
两边取log：log_2(2^a) <= log_2(n)，即a <= log_2(n)
所以外层循环的上限是log_2(n)，即它不能运行超过log_2(n)次。