时间戳

首页 > 解决方案 > while循环内排序的时间复杂度

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

问题描述

我正在尝试使用以下伪代码了解算法的时间复杂度：

让 nums 有数字的 ArrayList

sort(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)

现在这个算法的时间复杂度是多少。

标签： javaalgorithm

解决方案

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

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

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

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

在您的代码中，我们不知道Tsort 函数，只有它们的上限是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比较被忽略）

推荐阅读