这是什么时间复杂性？
这个问题在这里已经有了答案：
最坏的情况是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)如果你只是迭代一次而没有递归，基本上什么都不做。
平均情况是介于两者之间...我无法计算出这一个。
链接地址: http://www.djcxy.com/p/39363.html