Zeitkomplexität min num von Array

Question

Ich habe gerade angefangen Datenstrukturen & algos in Python zu lernen und kam auf folgende Frage:.

„zwei Python-Funktionen schreiben die Mindestanzahl in einer Liste finden Die erste Funktion jeden vergleichen sollte Nummer zu jeder anderen Nummer auf der Liste. O (n^2). Die zweite Funktion sollte linear O (n) sein. "

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

Getestet habe ich es mit einem Timer Dekorateur ich unten gemacht:

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

Dies ist das Ergebnis erhalte ich:

function: "findMin1" 
runtime: 0.03258419 sec 

function: "findMin1" 
runtime: 0.35547304 sec 

function: "findMin2" 
runtime: 0.035234928 sec 

function: "findMin2" 
runtime: 0.33552194 sec 

Offensichtlich linear ist besser, aber warum findMin1 wächst linear , nicht quadratisch wie erwartet?

Answer 1

Die return-Anweisung befindet sich innerhalb der äußeren for-Schleife. Daher führen Sie die äußere Schleife nur einmal aus und kehren dann sofort zurück. Deshalb hat die erste Methode die Komplexität O (n).

Wenn Sie return min_val einmal rückgängig machen und es außerhalb der äußeren for-Schleife verschieben, erhalten Sie quadratische Komplexität.