时间戳

首页 > 解决方案 > 经验性测量 QuickSelect 的时间复杂度

python - 经验性测量 QuickSelect 的时间复杂度

问题描述

我知道时间复杂度应该是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))

标签： pythonalgorithmtime-complexitycomplexity-theory

解决方案

insertPivot确实具有O(N)复杂性，因为您增加i和减少j直到j不再大于i. 但是，insertPivot是嵌入到while循环里面的quickselect。因此，无论 的复杂度如何quickselect，都会乘以 的复杂度insertPivot，因为在循环的每一步都会执行O(n)复杂度的算法。如果pivot < k - 1，则增加区间的左边界。否则你减少到pivot - 1. 因此，在循环中，您通过其左边缘和枢轴之间的差异来减少每一步的间隔大小。根据您可以使用什么函数来估算步数，您可以确定将线性复杂度中的 N 与什么相乘，从而得出实际复杂度。

推荐阅读