寻找有关如何计算 O (n log n) 复杂度的示例？
Looking for example on how to calculate complexity of O (n log n)?
我是数据结构的新手，一直在努力掌握这些概念。我了解 Big - O 表示法，并寻找与 O(n log n) 相关的示例。我在互联网上进行了搜索，但没有得到令人满意的示例或实现 - 在其中我可以看到 O(n log n) 的复杂性。
有人能给我指出一个更好的例子和实现吗？
提前致谢
O(nlogn) 算法的一个经典示例是 Merge Sort. Here you would find a detailed calculation of it's complexity. Generally speaking, there are many divide and conquer 具有这种复杂性的算法。
我建议查看 Cormen 的 Introduction to Algorithms Page-151 (Heapsort) 和 170 (Quicksort)。这些在本书中都有详细的解释。每种情况下的关键思想是您需要了解正在完成的基本操作，即比较（在这两种情况下），然后使用算法本身的特性进行分析。对于快速排序的关键分析和堆排序的堆化部分。
本书涵盖了分析复杂性所需了解的一切内容。
复杂性理论中有一个众所周知的定理，称为主定理。它的特殊情况是说如果一个算法的复杂度T(n)满足方程
T(n) = a T(n/a) + b*n (1)
然后
T(n) = O (n log n) (2)
上面的等式 (1) 可以解释为算法的工作原理是将问题拆分为 a 部分并将其自身分别应用于每个部分，然后对完整的输入进行一些处理。这种算法模式有时称为 合并和重组。
考虑以下 Python
中的示例
def f(x):
if len(x) > 1:
x1 = [z for z in x[1:] if z <= x[0]]
x2 = [z for z in x[1:] if z > x[0]]
return f(x1) + [x[0]] + f(x2)
else:
return x
此函数实现了一种递归算法，该算法将输入列表分成两部分，并将自身独立应用于每一部分，然后连接结果。如果幸运的话 x 和 y 部分长度相同，那么算法的复杂度可以用上面的公式 (2) 和 a = 2 来计算。
如果您熟悉排序和 Python 语言，您会在这里认出一种模拟快速排序但没有执行就地排序的复杂性的算法。一个更清晰的例子是 Christos 给出的答案中提到的合并排序。
我是数据结构的新手，一直在努力掌握这些概念。我了解 Big - O 表示法，并寻找与 O(n log n) 相关的示例。我在互联网上进行了搜索，但没有得到令人满意的示例或实现 - 在其中我可以看到 O(n log n) 的复杂性。 有人能给我指出一个更好的例子和实现吗？
提前致谢
O(nlogn) 算法的一个经典示例是 Merge Sort. Here you would find a detailed calculation of it's complexity. Generally speaking, there are many divide and conquer 具有这种复杂性的算法。
我建议查看 Cormen 的 Introduction to Algorithms Page-151 (Heapsort) 和 170 (Quicksort)。这些在本书中都有详细的解释。每种情况下的关键思想是您需要了解正在完成的基本操作，即比较（在这两种情况下），然后使用算法本身的特性进行分析。对于快速排序的关键分析和堆排序的堆化部分。
本书涵盖了分析复杂性所需了解的一切内容。
复杂性理论中有一个众所周知的定理，称为主定理。它的特殊情况是说如果一个算法的复杂度T(n)满足方程
T(n) = a T(n/a) + b*n (1)
然后
T(n) = O (n log n) (2)
上面的等式 (1) 可以解释为算法的工作原理是将问题拆分为 a 部分并将其自身分别应用于每个部分，然后对完整的输入进行一些处理。这种算法模式有时称为 合并和重组。
考虑以下 Python
中的示例 def f(x):
if len(x) > 1:
x1 = [z for z in x[1:] if z <= x[0]]
x2 = [z for z in x[1:] if z > x[0]]
return f(x1) + [x[0]] + f(x2)
else:
return x
此函数实现了一种递归算法，该算法将输入列表分成两部分，并将自身独立应用于每一部分，然后连接结果。如果幸运的话 x 和 y 部分长度相同，那么算法的复杂度可以用上面的公式 (2) 和 a = 2 来计算。
如果您熟悉排序和 Python 语言，您会在这里认出一种模拟快速排序但没有执行就地排序的复杂性的算法。一个更清晰的例子是 Christos 给出的答案中提到的合并排序。