Ama dilimlemede listenin bir kısmı kopyalanıyor. Zaman karmaşıklığını kastettiniz değil mi?
Evet, algoritmik dusunurkenki teorinin onemini vurgulayarak. Kopya degistirilip kullanilmiyorsa ve bu yuzden implementasyon O(n) bir islemi O(1) bir islemle hizlica degistirebilecekse algoritmanin o kismini O(1) varsaymanin zarardan cok faydasi var gibi geliyor. (Bunu her turlu kompleksite icin soyluyorum.)
Yoksa implementasyon detayina girersek tail-call optimization olmayan sistemlerdeki recursive her algoritma en az runtime kompleksitesi kadar hafiza kompleksitesine sahip.
Ben benim koda O(1) hafiza derdim mesela. Her kopya/slice icin gereken cagri basina 2 indexin tuttugu yer call stack devesinde kulak. Kocaman listenin kopyasi cikartilmiyor, onemli olan o.
2 Beğeni
O(n) ve O(1) nedir ayni zamanda lineer ne demek?
O(n) aşağıdaki gibi algoritmalar. Böyle algoritmalarda n girdi sayısı arttıkça, doğrusal zaman da buna paralel olarak artacaktır.
for i in liste:
print(i)
O(1) ise aşağıdaki gibi algoritmalar. Böyle algoritmalarda sabit zaman geçerlidir.
a = 5
b = 6
if a < b:
print(True)
else:
print(False)
1 Beğeni
Anladım …
Peki lineer ne demek?
O(n) algoritmalarda n sayısı arttıkça, işlemin gerçekleşme zamanı da n sayısına bağlı olarak artacaktır.
Örnek:
from timeit import timeit
def f(liste):
for i in liste:
print(i)
t1 = timeit(stmt="f([1])", globals=globals(), number=100000)
t2 = timeit(stmt="f([1, 2])", globals=globals(), number=100000)
print(t1/t2)
t1/t2 oranının 0.5’e yaklaştığını görürüz.
1 Beğeni