פייתון/פייתון גרסה 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$ מפני שבמקרה הגרוע ביותר יתרחש כאשר $l e n (x) < l e n (y)$ וגם $l e n (x) = l e n (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:])

סיבוכיות זמן : $n l o g n$ כי הפונקציה מחזירה את פונקצית foo פעמים ולכן אנחנו מקבלים חלוקה של הסדרה לשתי תתי סדרות עליהם מתבצעת כל התהליך. כל $f o o (x [: n / / 2])$ וגם $f o o (x [n / / 2 :])$ הם בעלי סיבוכיות של $l o g (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 (l o g (l e n (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 (l e n (b) + l e n (c))$

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

סיבוכיות זמן: $l o g (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 (l o g (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)

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

תפריט ניווט

חיפוש