Nasıl bir algoritma zaman karmaşıklığı bulmak için

SORU

14 HAZİRAN 2012, PERŞEMBE

Nasıl bir algoritma zaman karmaşıklığı bulmak için

Soru

Nasıl bir algoritma zaman karmaşıklığı bulmak için?

Benzeri bir soru göndermeden önce ne yaptım ?

this, this, this ve diğer birçok bağlantılar baktım

Ama hiçbir zaman karmaşıklığını hesaplamak için net ve yalındır bir açıklama bulabildim.

Ben ne biliyorum ki ?

Bir kod bu kadar basit için aşağıda ki:

char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time

Aşağıdaki gibi bir döngü için söylüyorlar

for (int i = 0; i < N; i  ) {        
    Console.Write('Hello World !');
}

i=0; intBu sadece idam edilecekbir kez. Zaman aslında i=0 ve beyan hesaplanmamış.

ben < N;Bu idam edilecekN 1kere

ben ;Bu idam edilecekNkere

İşlemleri bu döngü gerekli sayıda

{1 (N 1) N} = 2N 2

Not: Bu hesaplama hala zaman karmaşıklığı benim anlama konusunda emin değilim, yanlış olabilir

Ne bilmek istiyorum ?

Tamam, bu küçük temel hesaplamalar biliyorum, ama çoğu zaman karmaşıklığı gördük

O(N), O(n2), O(log n), O(n!).... other pek çok

Kimse bana nasıl bir algoritmanın zaman karmaşıklığını hesaplamak anlamanıza yardım edebilir mi? Benim gibi yeni başlayanlar bol bu bilmek isteyen vardır eminim.

CEVAP

18 Ocak 2013, Cuma

Bu mükemmel bir makale : http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

Aşağıda cevabını yukarıda mükemmel bağlantı büstü giderse () kopyalanır

Hesaplama zaman karmaşıklığı için kullanılan en yaygın ölçü, Büyük O gösterimi. Bu süre N sonsuza yaklaştıkça N ilgili olarak tahmin edilebilir, böylece tüm sabit faktörler kaldırır. Genel olarak şöyle düşünebilirsiniz:

statement;

Sürekli. Deyim süre N. ilgili olarak değişmez

for ( i = 0; i < N; i   )
     statement;

Doğrusal. Döngünün çalışma süresi N iki katına N. orantılı bir süre demek.

for ( i = 0; i < N; i   ) {
  for ( j = 0; j < N; j   )
    statement;
}

Karesel olur. İki döngüler çalışma süresi N iki katına, çalışma süresi * N. N tarafından arttığında N. karesi ile doğru orantılıdır

while ( low <= high ) {
  mid = ( low   high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid   1;
  else break;
}

Logaritmik olduğunu. Algoritmanın çalışma süresini N 2 ile bölünebilir sayısı ile doğru orantılıdır. Bu algoritma her yineleme ile yarım çalışma alanı böler olmasıdır.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot   1, right );
}

N * log ( N ). Çalışma süresi algoritma doğrusal ve logaritmik bir kombinasyonudur, bu nedenle logaritmik olan N döngüler (yinelemeli veya özyinelemeli) oluşur.

Genel olarak, bir boyutta her öğe ile bir şeyler yapmaya doğrusal, iki boyutlu her öğe ile bir şeyler yapmaya kuadratik ve yarım çalışma alanı bölme logaritmik. Kübik, üstel ve Karekök gibi diğer Büyük O tedbirler vardır, ama o kadar da yaygın değil. Büyük O gösterimi Ç olarak açıklanmıştır ( ) ölçüsüdür. Quicksort algoritması O ( N * log ( N)) olarak tarif edilir.

Bunların hiçbiri dikkate en iyi, ortalama ve en kötü durum önlemleri aldı unutmayın. Her biri kendi Büyük O onun işareti var. Ayrıca bu ÇOK basit bir açıklama olduğunu unutmayın. Büyük O, en yaygın, ama aynı zamanda gösterdim daha karmaşık. Ayrıca büyük omega, küçük o, ve büyük teta gibi diğer işaretler vardır. Muhtemelen onları algoritma analizi ders dışında karşılaşma olmayacak. ;)

Bunu Paylaş: