我已经比较了 python 3 中一些内置排序函数的性能和一些我知道它们的性能的算法，我看到了一些意想不到的结果。我想澄清这些问题。
我使用“perfplot”库来比较可视化算法的复杂性。
import numpy as np
import perfplot
# algorithms:
def sort(x):
np.sort(x)
return 0
def sort_c(x):
np.sort_complex(x)
np.sort_complex(x)
return 0
def builtin(x):
sorted(x)
return 0
def c_linear_inplace(x):
for i in range(len(x) - 1):
if x[i] > x[i + 1]:
x[i] = x[i] + x[i + 1]
x[i + 1] = x[i] - x[i + 1]
x[i] = x[i] - x[i + 1]
return 0
def c_linear_outplace(x):
a = x.copy()
for i in range(len(x) - 1):
if x[i] > x[i + 1]:
a[i] = x[i + 1]
a[i + 1] = x[i]
x = a.copy()
return 0
def c_nlogn(x):
logn = int(np.ceil(np.log2(len(x))))
for i in range(len(x)-1):
for j in range(logn):
x[i] = 0
return 0
#comprasion:
perfplot.show(
setup=np.random.rand, # function to generate input for kernel by n
kernels=[
sort,
sort_c,
builtin,
c_linear_inplace,
c_linear_outplace,
c_nlogn,
],
labels=["sort", "sort_c", "builtin", "check: linear inplace", "check: linear not in place", "check: nlogn"],
n_range=[2 ** k for k in range(15)], # list of sizes of inputs, i"setup" function will be called with those values
xlabel="len(a)",
)
我希望所有排序函数都接近 nlogn() 函数或至少比线性函数效率低，并且我希望“c_linear_inplace”会比“c_linear_outplace”快。但所有内置排序函数都比线性函数快得多，并且“c_linear_outplace”函数比“c_linear_inplace”函数慢。
编辑：
正如我所见，这些是具有常量的函数的复杂性：
sort，sort_c，builtin：c nlog 2 (n) for c>=1
check：linear inplace：6n
check：linear not in place：7n
check： nlogn : 2n + 3n对数2 n
我将任何 for 循环计算为 2*（迭代次数）以进行检查和增量。并且任何“if”都为 O(1)，任何赋值 (=) 为 O(1)，这似乎很奇怪，甚至占用更多内存的“check:linear not in place”比“check:linear inplace”的性能要好得多并且仍然比任何 numpy 的类型都差
