我有一段用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();
}
}
最糟糕的情况是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)如果您仅迭代一次而不进行递归，则基本上什么都不做。
平均情况介于两者之间……我无法计算出该情况。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句