0 00
Zaman karmaşıklığı lineer (linear time) algortima ne demektir?

Çalışma süresi T(n) girdi boyutuna göre (n) en çok doğrusal olarak artıyorsa böyle algoritmalara O(n) ya da lineer zamanlı algoritma denir.

Tanım
Zaman karmaşıklığı O(n) olan algoritmalara lineer zamanlı algoritma denir.

Lineer zamanlı algoritmaların çalışma süresi, girdilere (n) nispetle en fazla lineer (doğrusal) olarak olarak artar.

Örnek
Örneğin verilen bir sayıya (n) kadar olan bütün pozitif tam sayıların toplamını ekrana yazdıran bir algoritmanın çalışma süresi n ile doğru orantılıdır. 1'den 5'e kadar var olan bütün tam sayıların toplamını ekrana basmanın, 1'den 1000'e kadar olan tam sayıların toplamını ekrana basmaktan daha az zaman alacağı açıktır.
 
sum(5);
sum(1000);

function sum(n)
{
var total = 0; //t1
for(var i=1;i<=n;i++) //t2
    {
     total = total + i; //t3
    }
console.log(total); //t4
}

Analiz
Verilen algoritmanın zaman analizi yapıldığında çalışması için gerekli süre T(n) = 2n+2 olarak bulunur. Yani n=5 için 12 birim süre, n=1000 için 2002 birim süre zaman alır.
 
süre adım tekrar
t1 var total = 0; 1
t2 for(var i=1;i<=n;i++) n
t3 total = total + i; n
t4 console.log(total); 1

T(n) ⇒ O(n)
T(n) çalışma süresi fonksiyonu ile Büyük O notasyonu arasındaki geçişi incelemek için bu makaleye göz atınız.
Bu alana not ekleyebilirsiniz.
Başka bir sorunuz mu var?
Yorumlar (0)

Henüz yorum yapılmamış.

İlgili Konu
Algoritma Analizi
İlgili Kayıtlar
İlginizi Çekebilir