'警戒時間複雜度陷阱”

警惕時間複雜度陷阱

寫在這裡

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) -> 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 <= 0:
        return []

    max_heap = []

    for num in nums:
        if len(max_heap) < n:
            max_heap.append(num)
            # call sift_down
            for i in range((len(max_heap) - 2) // 2, -1, -1):
                _sift_down(max_heap, i)
        elif num > 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 < len(heap) and heap[left] > heap[largest]:
        largest = left

    if right < len(heap) and heap[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) -> 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 <= 0:
        return []

    max_heap = []

    for num in nums:
        if len(max_heap) < n:
            max_heap.append(num)
            # call sift_down
            for i in range((len(max_heap) - 2) // 2, -1, -1):
                _sift_down(max_heap, i)
        elif num > 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 < len(heap) and heap[left] > heap[largest]:
        largest = left

    if right < len(heap) and heap[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
使用Heapq：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
使用Heapq：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
使用Heapq：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
使用Heapq：0.0017773000290617347
Python 堆：20.780625900020823
排序：0.0017105999868363142

我發現了什麼以及如何改進它

當n很大時，Sorted會花費一點時間（有時甚至比使用heapq更好），但Python Heapq會花費很多時間。

• 為什麼Sorted花一點時間，而Python Heapq花很多時間？
• 因為sorted()是Python中內建的函數，所以你可以找到關於它的Python官方文件。

內建函數比 heapq 更快，因為它是用 C 寫的，C 是一種編譯語言。

• 如何改進？
• 您可以使用內建函數sorted()來取代heapq.sort()來提高程式碼的效能。 Sorted() 函數是 Python 中的內建函數，它是用 C 實現的，因此比 heapq.sort() 快得多

腦震盪

當我們處理大數據時，我們應該使用內建函數而不是 heapq.sort() 來提高程式碼的效能。在處理大數據時，我們必須警惕時間複雜度陷阱。有時時間複雜度的陷阱是不可避免的，但我們應該盡量避免它們。

關於我

大家好，我是夢沁園。我是一名學生。我喜歡學習新事物。
你可以看我的github：[MengQinYuan的Github][https://github.com/mengqinyuan]

以上是'警戒時間複雜度陷阱”的詳細內容。更多資訊請關注PHP中文網其他相關文章！