“警惕时间复杂度陷阱”

警惕时间复杂度陷阱

写在这里

一个bilibili视频也展示了这个：[bilibili视频][https://www.bilibili.com/video/bv16u4m1c7cu/?spm_id_from=333.999.0.0] 我觉得这是一个很好的视频，但它的语言是中文。

时间复杂度

时间复杂度是什么意思？
时间复杂度是算法运行所需时间的度量，作为其输入大小的函数。它是描述算法效率的一种方式，用于比较不同的算法并确定哪种算法最有效。
如何计算时间复杂度？
为了计算时间复杂度，我们需要将算法执行的操作数视为输入大小的函数。测量操作次数的最常见方法是计算特定操作执行的次数。
计算时间复杂度时有哪些常见陷阱？
1. 不考虑输入大小：如果我们只考虑算法执行的操作数量，我们可能会低估时间复杂度。例如，如果我们计算循环运行的次数，但不考虑输入的大小，那么时间复杂度可能会太高。
1. 不考虑算法的效率：有些算法即使输入量很小也可能会执行很多操作，这会导致时间复杂度很高。例如，冒泡排序和选择排序等排序算法具有二次时间复杂度，即使它们可能只需要交换小数组中的两个元素。
1. 不考虑算法的最坏情况：某些算法具有最好情况，其中执行的操作比最坏情况要少。例如，像二分搜索这样的搜索算法有一个最好的情况，即它们在对数时间内找到目标元素，但它们有一个最坏的情况，即它们需要检查数组中的所有元素。

让我们看一些时间复杂度的例子

这里有一个问题：
找出列表中最多 10 个整数。

import random
ls = [random.randint(1, 100) for _ in range(n)]

登录后复制

这是测试功能：

import time
def benchmark(func, *args) -&gt; float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

登录后复制

解决方案1：使用堆

这是使用 heapq 模块的解决方案：

def find_max_n(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

登录后复制

或者我们用python的方式来写：

def find_largest_n(nums, n):
    if n  max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index

    if left  heap[largest]:
        largest = left

    if right  heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)

登录后复制

解决方案2：使用排序

这是使用排序功能的解决方案：

def find_max_n(ls, n):
    return sorted(ls, reverse=true)[:n]

登录后复制

几乎所有人都知道，堆的时间复杂度是 o(n log k)，排序函数的时间复杂度是 o(n log n)。

看来第一个解决方案比第二个更好。但在python中却不是这样。

看最终代码：

import time
def benchmark(func, *args) -&gt; float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

def find_max_n_heapq(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

def find_max_n_python_heap(nums, n):
    if n  max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index

    if left  heap[largest]:
        largest = left

    if right  heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)


def find_max_n_sorted(ls, n):
    return sorted(ls, reverse=True)[:n]

# test
import random
for n in range(10, 10000, 100):
    ls = [random.randint(1, 100) for _ in range(n)]
    print(f"n = {n}")
    print(f"Use    Heapq: {benchmark(find_max_n_heapq, ls, n)}")
    print(f"Python Heapq: {benchmark(find_max_n_python_heap, ls, n)}")
    print(f"Sorted      : {benchmark(find_max_n_sorted, ls, n)}")

登录后复制

我在python3.11 vscode中运行，结果如下：

n 不大

使用heapq：0.002430099993944168
python 堆：0.06343129999004304
排序：9.280000813305378e-05
n = 910
使用堆：9.220000356435776e-05
python 堆：0.07715500006452203
排序：9.360001422464848e-05
n = 920
使用堆：9.440002031624317e-05
python 堆：0.06573969998862594
排序：0.00012450001668184996
n = 930
使用堆：9.689992293715477e-05
python 堆：0.06760239996947348
排序：9.66999214142561e-05
n = 940
使用堆：9.600003249943256e-05
python 堆：0.07372559991199523
排序：9.680003859102726e-05
n = 950
使用堆：9.770004544407129e-05
python 堆：0.07306570000946522
排序：0.00011979998089373112
n = 960
使用堆：9.980006143450737e-05
python 堆：0.0771204000338912
排序：0.00022829999215900898
n = 970
使用堆：0.0001601999392732978
python 堆：0.07493270002305508
排序：0.00010840001050382853
n = 980
使用堆：9.949994273483753e-05
python 堆：0.07698320003692061
排序：0.00010300008580088615
n = 990
使用堆：9.979994501918554e-05
python 堆：0.0848745999392122
排序：0.00012620002962648869

如果n很大？

n = 10000
使用堆：0.003642000025138259
python 堆：9.698883199947886
排序：0.00107999995816499
n = 11000
使用heapq：0.0014836000045761466
python 堆：10.537632800056599
排序：0.0012236000038683414
n = 12000
使用heapq：0.001384599949233234
python 堆：12.328411899972707
排序：0.0013226999435573816
n = 13000
使用heapq：0.0020017001079395413
python 堆：15.637207800056785
排序：0.0015075999544933438
n = 14000
使用heapq：0.0017026999266818166
python 堆：17.298848500009626
排序：0.0016967999981716275
n = 15000
使用堆：0.0017773000290617347
python 堆：20.780625900020823
排序：0.0017105999868363142