פייתון/פייתון גרסה 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^{2})$

סיבוכיות מקום: o(n) מאחר שבכל פעם כאשר הפונקציה מקיימת את התנאי מתבצעת פונקציתappend מבצעת n פעמים ולכן סיבוכיות המקום $o(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))])

סיבוכיות זמן:$n-m+1$ מפני שבמקרה הגרוע ביותר יתרחש כאשר $len(x)<len(y)$ וגם $len(x)=len(y)-1$ כלומר כאשר $n=m-1$

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

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

סיבוכיות ריצה $o({\sqrt {n}})$ מפני שהטווח הוא בין $2,\dots ,(n-1)$. במקרה הגרוע ביותר מתקיים ש-$n$ מתחלק ב-$i$ שוב ושוב עבור כל המספרים בין $2,\dots (n-1)$. לדוג' אם $n=4$ אזי האינדקסים שלנו הם $2,\dots ,4$ ולכן ${\frac {4}{2}},{\frac {4}{1}}$ יחזיר אמת ועל ${\frac {4}{3}}$ שקר. לעומת זאת עבור $n=3$ אז נקבל ש-${\frac {3}{2}}$ שקר ואילו ${\frac {3}{3}}$ אמ

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

סיבוכיות זמן :$nlogn$ כי הפונקציה מחזירה את פונקצית foo פעמים ולכן אנחנו מקבלים חלוקה של הסדרה לשתי תתי סדרות עליהם מתבצעת כל התהליך. כל $foo(x[:n//2])$ וגם $foo(x[n//2:])$ הם בעלי סיבוכיות של $log(n)$ וסה"כ החלוקה לשנים תלוי באורך הסדרה $n$

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

סיבוכיות זמן: $o(n^{2})$

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

סיבוכיות זמן: $o(log(len(a)))$

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

סיבוכיות זמן: $o(len(b)+len(c))$

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

סיבוכיות זמן: $log(n)$

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

סיבוכיות זמן $o(2^{n})$

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

סיבוכיות זמן: $O(n)$

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)

סיבוכיות זמן: $o(log(n))$

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

סיבוכיות זמן: $o(n^{1.5})$

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)