我正在阅读此问题，而此评论恰好吸引了我的注意力Stackoverflow
注释说，为了达到O(n log n)，我们需要将外部循环设为:for(int i = 0; i < n; i++)，将嵌套循环设为:for(int j = n; j > 0; j/=2)，这将使嵌套循环域从n变为n / 2。
我了解要找到时间复杂度，我们会考虑输入大小以及运行计算所需的步骤数，但在我看来，这完全取决于逐步的部分以及如何最小化从0到n的步数(反之亦然)。我的理解正确吗？
如果为真，则将嵌套循环更改为for(int j = n/2; j > 0; j--)或for(int j = n/4; j > 0; j--)(这将使域分别介于0和n / 2或n / 4之间)仍将保持算法复杂度为n*(n/2) or n*(n/4) = n^2
我感谢任何解释。
最佳答案
...使嵌套循环域从n到n / 2。
那不是很正确。循环仍然从n变为0；域没有改变。改变的是它如何到达那里。它不会在每次迭代中减去一个，这意味着将需要n步骤。每次迭代将j分成两半。
在达到0之前，您可以将数字除半数几次？好吧，如果您从n开始，则需要O(log2 n)步骤。
每次您将n加倍，都需要再走一步。经典指数/对数关系。
这个教训是:在迭代步骤中进行除法有很大的不同...
for(int j = n; j > 0; j/=2) // O(log n)
...并使其处于开始或结束范围:
for(int j = n/2; j > 0; j--) // O(n/2) = O(n)
for(int j = n; j > n/2; j--) // O(n/2) = O(n)
关于java - 算法的时间复杂度取决于增量/减量步长部分，而不取决于实际输入大小？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59309849/