פייתון/פייתון גרסה 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