時間min陣列

Question

的NUM複雜我剛開始學習數據結構在Python &交易算法並在以下問題來了：

「寫兩個Python功能來查找列表中的最小數量的第一功能應該比較各編號到列表中的每個其他數字O（n^2）。第二個函數應該是線性的O（n）。「

# ./misc/decorator_timer.py 

import time 
from functools import wraps 


def my_timer(func): 
    """Adds how long it took to run""" 

    @wraps(func) 
    def wrapper(*args, **kwargs): 
     t0 = time.time() 
     result = func(*args, **kwargs) 
     timedelta = time.time() - t0 

     print(f'\nfunction:\t"{func.__name__}"\nruntime:\t {timedelta:.08} sec') 

     return result 

    return wrapper 

這是結果我得到：

from misc.decorator_timer import my_timer 


def main(): 
    """ 
    Finds the minimum number in a list 
    findMin1: O(n^2) 
    findMin2: O(n) 
    """ 
    findMin1(list(range(10**6))) 
    findMin1(list(range(10**7))) 
    findMin2(list(range(10**6))) 
    findMin2(list(range(10**7))) 


@my_timer 
def findMin1(array): 
    """Finds min number in a list in O(n^2) time""" 
    for i in range(len(array)): 
     min_val = array[i] 
     for num in array: 
      if num < min_val: 
       min_val = num 
     return min_val 


@my_timer 
def findMin2(array): 
    """Finds min number in a list in O(n) time""" 
    min_val = array[0] 
    for num in array: 
     if num < min_val: 
      min_val = num 
    return min_val 


if __name__ == '__main__': 
    main() 

我有計時器裝飾我下面進行測試它

function: "findMin1" 
runtime: 0.03258419 sec 

function: "findMin1" 
runtime: 0.35547304 sec 

function: "findMin2" 
runtime: 0.035234928 sec 

function: "findMin2" 
runtime: 0.33552194 sec 

顯然線性較好，但爲什麼是findMin1線性增長，不像預期的那樣呈現二次曲線？

Answer 1

return語句位於outer for循環內部，因此您只執行一次外循環，然後立即返回。因此，第一種方法具有複雜性O（n）。

如果您取消縮進return min_val一次，將它移動到外部for循環之外，則會產生二次複雜性。