Python中嵌套在内置方法中的模块的大O表示法

Question

我想知道在Python中确定内置方法背后的大O值的基本原理。给出以下操作：

i_arr = ['1','2','5','3','4','5','5']

s_arr = sorted(set(i_arr))

我的基本原理是sorted(set) = n^2表示两个嵌套循环。在

根据建议，我在Python源代码中挖掘了更高级别的模块作为我原始函数的一部分：

^{pr2}$

现在我真的很困惑：）

Answer 1

排序算法复杂度的上界一般为O（n*log（n）），如wikipedia所示。 然后取决于将数组强制转换到集合需要多长时间。从您发布的示例中，我们可以看到列表被迭代，并且在每个步骤中，值都被检查是否已经在集合中。 根据this对集合中元素存在性的检验具有恒定的复杂度O（1），因此集合的整个构造由于迭代所有元素而具有复杂度O（n）。 但是假设它是通过一个接一个地添加每个元素来实现的，我们必须遍历list将它转换成集合，它是O（n*log（n）），然后我们对它进行排序，得到总复杂度O（n*log（n）+n）=O（n*log（n））。在

更新：

映射也具有线性复杂性，因为它迭代整个集合并映射每个元素，但是由于线性函数的增长速度慢于n*log（n），这里的任何线性运算都不会影响O（n*log（n）），因此即使是映射，渐近复杂度也保持不变。在

Answer 2

（N logN）是一些排序算法的下限，如快速排序、堆排序、合并排序。它们是基于比较的通用算法。在最坏的情况下，它可以是O（N*N）。在

如果元素是数值型的，则有O（N）上界算法可用，如基数排序、计数排序和桶排序。在

如果我们讨论的是python库的“sorted”实现，即TimSort实现。TimSort是一种优化的mergesort算法。它比常规的mergesort算法稳定、速度快。它在最坏的情况下运行于O（N logn），在最佳情况下运行于O（N）（当列表已经排序时）。在

Answer 3

除了“泛型排序”的性能问题之外，正如您提到的sorted()，我假设您在询问python中内置方法背后的大O值。在

好吧，python使用了Timsort；并引用了维基百科：

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

In the worst case, Timsort takes O(n log n) comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm.