JavaScript数组场景下大O表示法时间复杂度判定求助

我太懂这种困惑了——大O表示法刚接触的时候真的绕得慌，看再多视频可能也没戳中你卡壳的点。咱们直接对着你的代码拆解，保证你能get到！

先看你这段代码的核心逻辑（本质就是选择排序的实现）：

function sortSmallestToLargest(entries):
    sorted_entries = {}
    while entries is not empty:
        smallest_entry = entries[0]
        foreach entry in entries:  # 这是内层循环
            if (entry < smallest_entry):
                smallest_entry = entry
        sorted_entries.add(smallest_entry)
        entries.remove(smallest_entry)
    return sorted_entries

推导思路： #

咱们从操作次数的角度算：

• 第一次进入while循环时，entries里有n个元素，内层的foreach要把所有n个元素遍历一遍，才能找到最小的那个；
• 找到最小元素并移除后，entries剩下n-1个元素，第二次while循环时，内层foreach要遍历n-1次；
• 第三次循环，entries剩n-2个元素，内层遍历n-2次；
• ……
• 最后一次循环，entries只剩1个元素，内层遍历1次。

把所有遍历次数加起来，就是：
n + (n-1) + (n-2) + ... + 1

这个求和的结果是n(n+1)/2，展开后是(1/2)n² + (1/2)n。

而大O表示法的规则是：

1. 只保留最高次项（这里最高次是n²）；
2. 忽略最高次项的系数（这里的1/2直接去掉）；
3. 扔掉低次项和常数项（这里的(1/2)n直接忽略）。

所以最终的时间复杂度就是O(n²)。

顺便帮你排除其他选项： #

• O(n)：是线性复杂度，比如只遍历一次数组的操作，显然你这段代码嵌套了循环，不可能是O(n)；
• O(logn)：是对数复杂度，比如二分查找这种每次把问题规模减半的操作，你这里没有“减半”的逻辑，排除；
• O(nlogn)：比如归并排序、快速排序（平均情况），这类算法是把问题拆成logn层，每层处理n个元素，你这段代码没有分层拆分的逻辑，所以也不是。

内容的提问来源于stack exchange，提问作者KeenLearnerA