<分区>
int sum = 0;
for (int n = N; n > 0; n /= 2)
for(int i = 0; i < n; i++)
sum++;
int sum = 0;
for (int i = 1 i < N; i *= 2)
for (int j = 0; j < i; j++)
sum++;
int sum = 0;
for (int i = 1 i < N; i *= 2)
for (int j = 0; j < N; j++)
sum++;
这个问题困扰我好久了。我还是一名大二学生，但我仍然无法计算算法的复杂度。我该如何计算？我觉得自己很无能，因为我似乎从来没有得到它!
例如，for 循环的复杂度是否总是 N？怎么知道？你能推荐我可以阅读的任何资源吗？有视频吗？
最佳答案
你的第一个和第二个例子是一样的(就时间复杂度而言)。对于他们来说，时间复杂度是 O(N)。为什么。让我们计算一下。对于第一个示例，您的内部循环运行 N 次，然后运行 N/2 次，然后运行 N/4 并上升到 1。因此，时间复杂度为 O(N+N/2+N/4+..+1 ) 并且此 GP 的总和为 (2n-1)。因此，第一种情况的时间复杂度为 O(N)。
对于第二个例子，你的内循环运行了 1 次，然后 2 次，4 次，一直到 N。所以，时间复杂度是 O(1+2+4+...+N) 和 sum此 GP 的 2log(N+1)-1 等于 N。因此，第二种情况的时间复杂度也是 O(N)。
对于第三个示例，第一个循环运行 log(N) 次，内部循环运行 N 次，由于它们各自独立，因此所需的时间复杂度为 O(NlogN)。 (所有计算均为近似值，所有对数基数均为2)
好吧，要了解 for 循环的时间复杂度，您必须查看“i”被分配了多少次值(可以相同或不同)。
要了解时间复杂度，请查看 hackerearth 资料，每次编写算法时，请尝试计算其时间复杂度。这是学习它并检查递归关系的 Masters 定理的最佳方法，但也要了解它的基础知识。
关于java - 如何计算算法的复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53904872/