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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

דוגמה 1[עריכה]

def half_len(n):

    while n>1:
        n = n/2

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

על כן, אנו מחלקים שוב ושוב בשתיים ולכן פעולת החילוק היא (נזכיר בלוגריתם . במקרה שלנו אנו רוצים את הפעולה ההפוכה לחזקה ולכן ) ומספר הפעמים שמבוצע פעמים כלומר התכנית כולה תרוץ

דוגמה 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