java在这方面的时间复杂度是多少？

Question

我有一段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();
    }
}

Answer 1

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

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)如果您只迭代一次而没有递归，基本上什么也不做

平均病例数介于。。。我不能计算那个