פייתון/פייתון גרסה 3/סיבוכיות/אוסף דוגמאות

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש
def has_cycle(head):
    past = []
    cur=head
    while cur is not None:
        for cur in past:
            return True
        past.append(cur)
        cur =cur.next
    return False

סיבוכיות זמן: o(n^2) כי עבור כל לולאת while יש n פעמים פעולות וכאשר המתקיים התנאי מתבצע עוד n פעמים הפעולה. סיבוכיות הזמן המקסימלית היא

סיבוכיות מקום: o(n) מאחר שבכל פעם כאשר הפונקציה מקיימת את התנאי מתבצעת פונקציתappend מבצעת n פעמים ולכן סיבוכיות המקום

def bar(x,y,z):
    if len(x) < len(y):
        return False
    elif foo(x,y) <= z:
        return 
    else:
        return bar(x[1:],y,z)
def foo(x,y): 
return g([f(x[i],y[i]) for i in range (len(y))])

סיבוכיות זמן: מפני שבמקרה הגרוע ביותר יתרחש כאשר וגם כלומר כאשר

סיבוכיות מיקום: לפי השורה האחרונה פונקצית g מחזירה n מקומות

def sreach(n):
    for i in range(2, n):
        if n%i == 0:
            return True
        if i>n/i:
            return False

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

def foo(x):
    n = len(x)
    if n<=1:
        return 17
    return foo(x[:n//2])+foo(x[n//2:])

סיבוכיות זמן : כי הפונקציה מחזירה את פונקצית foo פעמים ולכן אנחנו מקבלים חלוקה של הסדרה לשתי תתי סדרות עליהם מתבצעת כל התהליך. כל וגם הם בעלי סיבוכיות של וסה"כ החלוקה לשנים תלוי באורך הסדרה

def f(n):
    sum=0
    i=0
    while i<n:
        i=i+1
        for j in range(n):
            sum=sum + j

סיבוכיות זמן:

def find(x,a):
    l, h = o, len(a)
    while l<n:
        m = (l+h)//2
        if x == a[m]:
            return True, m
        if x<a[m]:
            n=m
        else:
            l=m+1
    return False, 1

סיבוכיות זמן:

def merge(b,c,a):
    i,j,k = 0,0,0
    while k<len(a):
        if b[i] < c[j] :
            a[k] = b[i]
            i = i+1
            k=k+1
        else:
            a[k] = b[i]
            j=j+1
            k=k+1

סיבוכיות זמן:

def f(n):
    while n>1:
        n=n/2

סיבוכיות זמן:


def f(n):
    sum = 0
    for i in range(2^n):
        sum = sum + i

סיבוכיות זמן

def f(n):
    a = [o]*n
    for i in reange(n):
        a[i]=1
    for i in range(n):
        found - i in a

סיבוכיות זמן:

def atgmin(a,start):
    index = start
    for i in range(start +1, len(a)):
        if a[i]< a[index]:
            index = i
    return index

def sort(a):
    for i in range(len(a)):
        small = argmin(a,i)
        a[i], a[small] = a[small], a[i]
def funny(n):
   if n<= 6:
       return 7
    return funny(n//8) + funny(4)

סיבוכיות זמן:

def loopy(n):
    for i in range(len(n)):
        for j in range(i):
            if j*j>i:
                break

סיבוכיות זמן:

def f1():
   a=[]
   for j in range(100000):
       a.append(j*j)

   for j in range(100000):
       if 99999*j == a[j]:
           print(yes)
def f2():
   a=[]
   for j in range(100000):
       a.append(j*j)

   for j in range(100000):
       if 99999*j == a[j]:
           print(yes)

def f3():
    d = {}
    for j in range(100000):
       d[i] = j*j

   for j in range(100000):
       if 99999*j in d:
          print(yes)