Zaman Karmaşıklığı Nedir?

Zaman karmaşıklığı nedir?

Zaman karmaşıklığı, bir algoritmanın veri büyüdükçe ne kadar daha fazla iş yaptığını gösteren ölçüdür. Saniye ölçmek yerine adım sayısı sayılır, çünkü aynı kod hızlı bir bilgisayarda ve eski bir dizüstünde farklı sürede çalışır. Adım sayısının girdiyle nasıl büyüdüğü ise donanımdan bağımsızdır.

Nasıl hesaplanır?

Temel yöntem, kodun kaç kez tekrarlandığına bakmaktır. Tek bir işlem, örneğin iki sayıyı toplamak, sabit sürelidir ve O(1) yazılır. n elemanlık bir listeyi baştan sona dolaşan bir döngü n adım atar ve O(n) olur.

İç içe döngüler çarpılır. Bir sınıftaki 30 öğrencinin her birini diğer 30 öğrenciyle karşılaştıran kod 900 adım atar; genel hâliyle bu n × n, yani O(n²) demektir. Her adımda veriyi yarıya indiren bir döngü ise O(log n) sürede biter. Ardışık bloklar toplanır ve sonuçta en hızlı büyüyen terim tutulur. O(n) bir döngünün ardından O(n²) bir döngü varsa, toplam karmaşıklık O(n²) kabul edilir.

En iyi, ortalama ve en kötü durum

Aynı algoritma farklı girdilerde farklı davranabilir. Doğrusal arama aranan değer ilk sıradaysa tek adımda biter; bu en iyi durumdur. Değer sonda ya da hiç yoksa n adım gerekir; bu da en kötü durumdur. Pratikte en kötü durum esas alınır, çünkü sistemin yoğun yük altında nasıl davranacağını o gösterir.

Neden önemsemelisiniz?

Kullanıcı sayısı 100'den 100.000'e çıkan bir uygulamada, O(n²) bir rapor sorgusu dakikalar sürmeye başlayabilir. Bu tür yavaşlamaların kökü çoğu zaman bir iç içe döngüdür. Kodunuzu yazarken her döngü için "bu kaç kez çalışacak?" sorusunu sormak, sorunları büyümeden yakalamanın en ucuz yoludur.