Algoritmalarin kompleksitesi

Question

Ilgili soruda $1..k$ sayilarini bolen en kucuk sayiyi bulan iki algoritma var:

def is_prime(n) :
    for i in range(2,int(n**0.5)+1) :
        if n % i == 0 :
            return False
    return True



def algoritma1(k):
    i=2
    A=1
    while i <= k :
        if is_prime(i) :
            a = int(math.log(k) / math.log(i))
            A = A * (i**a)
        i += 1
    return A


def ebob(a, b):
    for c in range(min(a, b), 0, -1):
        if a % c == b % c == 0:
            return c

def ekok(a, b):
    return abs(a*b) // ebob(a, b)

def algoritma2(k):
    ret = 1
    for i in range(1,k+1):
       ret = ekok(i,ret)
    return ret

 

Bu iki algoritmanin kompleksitelerini (verilen bir $k$ sayisina gore algoritmanin yaptigi islem kabaca ne kadar degisiyor) karsilastirabilir misiniz?

Comments

belli bir k değeri için harcanan zamanı ölçebiliriz: pythonda %%time kodu ile şöyle yapıyoruz: 

%%time
# kod satırlarınızı aşağı yazıp çalıştırın.


# çıktınızda harcanan zaman da görünecektir.

 

Bunu her bir algoritmaya uygulayarak harcadıkları zamanları ölçebilirsiniz.

---

Evet boyle bir deney yapabiliriz ama bu deneyin sonucu kullandigimiz bilgisayara/bilgisayarda acik olan programlara vb. vb. ye bagli olacak. Benim istedigim aslinda kalem kagit ile dusunmek bu algoritma da $n$ yi degistirdigimde algoritmanin calisma suresi/hafizasi $n$ e bagli olarak nasil degisiyor.

 bkz:zaman karmasikligi  ve alan karmasikligi