פייתון/פייתון גרסה 3/סיבוכיות/סיבוכיות זמן/סיבוכיות לוגריתמית

דוגמה 1

def half_len(n):

    while n>1:
        n = n/2

במקרה זה אנו מכניסים אל הפונקציה מספר וחותכים אותו בחצי פעם אחר פעם. לדוגמה, אם נכניס את המספר חמש, נחלק בשתים ונקבל 2. נחלק שוב את שתים ונקבל אחד - הלולאה מפסיקה.

על כן, אנו מחלקים שוב ושוב בשתיים ולכן פעולת החילוק היא $log$ (נזכיר בלוגריתם $a^{b}=x\iff \log _{a}x=b$. במקרה שלנו אנו רוצים את הפעולה ההפוכה לחזקה ולכן ) ומספר הפעמים שמבוצע $n$ פעמים כלומר התכנית כולה תרוץ $o(logn)$

דוגמה 2

ראשית קרא על האלגוריתם חיפוש בינארי.

def binary_search(lst, value):
    '''a binary search'''
    
    low = 0 high = len(lst) 

    while high > low:
        mid = (high+low)//2
        if lst[mid] == value:
            return mid
        elif lst[mid] < value:
            low = mid + 1
        else:
            high = mid
    return -1