时间戳

首页 > 解决方案 > 计算算法时间复杂度的方法

sorting - 计算算法时间复杂度的方法

问题描述

虽然有点熟悉直观地确定算法的复杂性，但我对如何实际计算它有点迷茫。

对于以下代码，知道如何确定复杂性吗？

list = [...]
start = list[0]
end = null 
remove list[0] from list

while(list.length > 0) {
  for(i = 0; i < list.length; i++) {
    if(list[i] is immediately before start or immediately after end) {
       link list[i] to start or end (populate end if null)
       remove list[i] from list
    } 
  }
}

这假设一个有效的数据集（必须排序的元素的连续链接列表）。出于说明目的也进行了简化；

因此，如果列表已经排序，最好的情况是 O(n)，因为您只需要通过来处理它们并将它们弹出。

我无法确定的是最坏的情况，因为每次“while”迭代数据集都会减小至少 1 个元素（通常是 2 个或更多），因为假设数据集将始终有效。所以它显然小于 O(n^2) （我认为）。欢迎所有想法。

谢谢！

更新 绘制出来后，它似乎是 O(nlogk(n)) where k = n ^ (2/(n+1)) 这算作 O(nlog(n)) 吗？我不清楚。

标签： sortingtime-complexity

解决方案

大 O 表示法旨在为函数的增长率提供上限，因此您必须考虑最坏的情况。

在最坏的情况下，我会假设在每次迭代中，数据集会变小 1 个元素，因此您要执行的操作数量将受其约束，n + n-1 + n-2 ... + 2 + 1即(n+1)*n / 2O(n^2)

推荐阅读