QuickSelect时间复杂度的经验测量

Question

我知道时间复杂度应该是O(N)。然而，当我对它进行经验测试时，我得到了奇怪的结果。有人能解释一下发生了什么事吗？

def insertPivot(array, start, end):
    pivot = end
    i = start
    j = end - 1

    while i < j:
        while array[i] < array[pivot] and i < j:
            i += 1
        while array[j] > array[pivot] and j > i:
            j -= 1
        array[i], array[j] = array[j], array[i]
    
    if array[i] > array[pivot]:
        array[i], array[pivot] = array[pivot], array[i]
        pivot = i
    
    return pivot
    
def quickselect(array, k):
    start = 0
    end = len(array) - 1
    pivot = insertPivot(array, start, end)
    while pivot != k - 1:
        if pivot < k - 1:
            start, end = pivot, end
        else:
            start, end = start, pivot - 1
        pivot = insertPivot(array, start, end)
    return array[k - 1]

这是我如何得到我的尺寸

import random
import timeit
import numpy as np

av_times = dict()
for n in [10, 100, 500, 1000, 5000, 10000]:
    times = list()
    array = list(range(n))
    for _ in range(10):
        random.shuffle(array)
        k = random.randint(0, n)
        times.append(
            timeit.timeit(lambda: quickselect(array, k), number=10)
        )
    av_times[n] = sum(times) / len(times)

xx, yy = zip(*av_times.items())
xx, yy = np.log(xx), np.log(yy)
m, b = np.polyfit(xx, yy, 1)

斜率系数m为1.5，时间复杂度为O(N*sqrt(N))

Answer 1

insertPivot实际上是O(N)复杂度，因为您增加了i并减少了j，直到j不再大于i。但是，insertPivot被嵌入到quickselect中的while循环中。因此，无论quickselect的复杂度有多高，都会使insertPivot的复杂度成倍增加，因为在循环的每一步上都会执行O(n)复杂度的算法。如果为pivot < k - 1，则增加间隔的左边界。否则，您将减少到pivot - 1。因此，在循环中，您可以通过右边缘的左侧和轴心之间的差来减小每一步的间隔大小。根据您可以使用什么函数来近似步数，您可以确定在线性复杂度中将N乘以什么，从而导致实际复杂度。