为什么O(NlogN)算法在leetcode上比O(N)算法表现更好？

Question

我在 leetcode 上解决一个问题，发现 O(NlogN) 算法的性能比 O(N) 更好。

https://leetcode.com/problems/sort-characters-by-Frequency

解决方案1：

    def frequencySort(self, s: str) -> str:
        return ''.join(char * occurences for char, occurences in Counter(s).most_common())

leetcode 分析复杂度

运行时

解决方案2：

    def frequencySort(self, s: str) -> str:
        count = Counter(s)
        buckets = defaultdict(list)

        for char, cnt in count. items(): 
            buckets[cnt].append(char)
        res = []

        for i in range(len(s), 0, -1): 
            for c in buckets[i]:
                res.append(c * i)

        return "".join(res)

leetcode 分析复杂度

运行时

Answer 1

一般来说，时间复杂度为 O(N) 的算法被认为比时间复杂度为 O(N log N) 的算法更高效。

首先，为了更好地思考，让我们看看哪些算法遵循 O(N log N) 时间复杂度。 一些算法的时间复杂度为 O(n log n)。以下是一些示例：

Merge sort, Heapsort, Quick sort, Binary Search Tree (BST), Dijkstra's, K-way Merge, Median Finding, Closest Pair, K-means clustering, Range searching

原因是，随着输入大小 (N) 的增加，O(N) 算法的运行时间随 N 线性增长，而 O(N log N) 算法的运行时间由于对数因素而增长得更快。

为了说明这一点，让我们考虑一个例子：

假设我们有两种算法：

算法A：O(N)算法，运行时间10N毫秒 算法B：O(N log N)算法，运行时间为5N log N毫秒

对于较小的输入大小，算法 B 可能会更快。例如，当 N = 100 时：

算法A：10N = 1000 毫秒 算法B：5N log N = 500 log 100 ≈ 1150 毫秒

但是，随着输入大小的增加，性能差异变得更加明显：

当 N = 1000 时：

算法A：10N = 10,000 毫秒 算法B：5N log N = 5000 log 1000 ≈ 15,000 毫秒

如您所见，随着输入大小的增加，算法 A (O(N)) 的速度明显快于算法 B (O(N log N))。

因此，一般来说，对于大输入量，O(N) 算法预计比 O(N log N) 算法表现更好。

如果在特定场景中 O(N log N) 算法的性能优于 O(N) 算法，则可能还有其他因素在起作用，例如：

缓存效率 内存访问模式 实施细节 数据分布 在这种情况下，有必要分析具体的算法实现和底层系统架构，以了解性能差异。