时间复杂度最小数组数

Question

我刚开始在 Python 学习数据结构和算法，并遇到了以下问题：

"Write two Python functions to find the minimum number in a list. The first function should compare each number to every other number on the list. O(n^2). The second function should be linear O(n)."

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()

我用下面制作的计时器装饰器对其进行了测试：

# ./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

这是我得到的结果：

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 语句在外循环中，因此您只执行一次外循环，然后立即return。因此，第一种方法的复杂度为 O(n)。

如果你取消缩进 return min_val 一次，将它移到外部 for 循环之外，你会得到二次复杂度。

时间复杂度最小数组数

Time complexity min num of array

python

arrays

time

decorator

min