java - 时间的复杂度是多少？

This question already has answers here:

Big O, how do you calculate/approximate it?
                                
                                    （23个答案）
                                
                        
                                去年关闭。
            
                    
我有一段用Java写的代码，我一直在努力理解什么是时间复杂性...
在最好的情况下，我相信可能是O（n），最坏的情况可能是O（n ^ 2），因为它可以递归n次。
这是正确的吗？？

所有其他方法均为O（1）

public void associateblocks() {
    Block block = head;
    while (block != null) {
        Block block2 = block.getNextBlock();
        if (block2 != null) {
            if (block.getSize() == block2.getSize() && block.isFree() && block2.isFree()) {
                block.setSize(block.getSize() * 2);
                block.setIndex((block.getIndex() - 1) / 2);
                block.setNextBlock(block2.getNextBlock());
                associateblocks();
                freeBlocks.remove(block2);
            }
        }
        block = block.getNextBlock();
    }
}

最佳答案

如果假定所有块都是“空闲”的，并且它们的大小以2的幂减小，最后两个为1，则最坏的情况是O(n^2)：

2^n, 2^(n-1) ... , 64, 32, 16, 8, 4, 2, 1, 1

第一次迭代将最后两个合并，触发一个递归调用，该调用现在作用于一个看起来像

2^n, 2^(n-1) ... , 64, 32, 16, 8, 4, 2, 2

合并最后两个，递归调用，现在在

2^n, 2^(n-1) ... , 64, 32, 16, 8, 4, 4

等等。第一次循环n，然后循环n-1，n-2，...对所有得到n * (n + 1) / 2步骤或O(n^2)的结果求和。

最好的情况是O(n)，如果您仅迭代一次而不进行递归，则基本上什么也不做。

平均情况介于两者之间。