while循环内排序的时间复杂度

Question

我试图用下面的伪代码来理解算法的时间复杂度：让 nums 有数字的 ArrayListsort(nums)while(nums.size() > 1) {   // remove two elements   nums.remove(0);   nums.remove(0);   nums.add(some_number);   sort(nums);}sort(nums)是(N)Log(N)。 nums.remove(0)是O(N) nums.add()是O(1)现在这个算法的时间复杂度是多少。

Answer 1

最终的复杂性是O(n² log n)因为您执行了n多次操作O(n log n)。

请记住，估计复杂度 ( O(...)) 与建立操作总数不同（通常时间函数T(...)由操作总数给出），它们是两个不同的概念。算法分析是一个很好的介绍

因此，O(...)符号是上限，但却T(...)是真实的步骤。

您可以尝试精确计算T函数，也可以通过改进 来降低上限O，但它们始终是不同的函数，这O适用于所有可能条目的最坏情况。

在您的代码中，我们不知道T排序函数，只有它们的上限是O(n log n)，那么：

T(n) ≤ O(n log n) + T(3) + O((n - 1) log (n - 1)) + T(3) + O((n - 2) log (n - 2) + ...

T(n) ≤ O(n log n) + n T(3) + n O(n log n)

                               ^^^^^^^^^

在这里，我们无法准确定义、 、 ...T上的排序操作，这就是为所有这些操作建立更高级别的原因。然后：n-1n-2O(n log n)

T(n) ≤ O(n log n) + n T(3) + n O(n log n)

T(n) ≤ O(n log n) + O(n) + O(n² log n)

T(n) ≤ O(n² log n)

在第二个表达式中，我们有固定数量的上限，在这种情况下，上限将是上限中的最高者。

（删除、删除和添加 is T(3)，goto比较被忽略）