Algoritmanın zaman karmaşıklığı nasıl bulunur

soru

Algoritmanın zaman karmaşıklığı nasıl bulunur?

SO sorusunu yayınlamadan önce ne yaptım?

Bunu, bunu ve diğer pek çok bağlantıyı geçtim

Ama hayır, zamanın karmaşıklığını nasıl hesaplayacağımızın açık ve doğrudan bir açıklamasını bulabileceğim bir yer.

Ne biliyorum

Kodun aşağıdaki kadar basit olduğunu söyleyin:

 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ü söyleyin:

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

int i = 0; Bu sadece bir kez yapılacaktır . Zaman gerçekte bildirimi değil, i=0 hesaplanır.

i <n; Bu N + 1 kez yapılacaktır.

I ++ Bu N kez yapılacaktır.

Dolayısıyla, bu döngünün gerektirdiği işlem sayısı

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

Not. Bu yanlış olabilir, çünkü zamansal karmaşıklığı hesaplarken anladığımdan emin değilim.

Ne bilmek istiyorum

Tamam, bu yüzden bu küçük temel hesaplamalar, sanırım biliyorum, ama çoğu zaman zaman karmaşıklığı gördüm, çünkü

O (N), O (n2), O (log n), O (n!) .... ve diğerleri ,

Birisi bana algoritmanın zaman karmaşıklığını nasıl hesaplayacağımı anlamam için yardımcı olabilir mi? Eminim ki benim gibi bilmek isteyen bir sürü yenisi vardır.

724
14 июня '12 в 14:21 2012-06-14 14:21 Yasser , 14 Haziran 12'de, saat 02:21 de ayarlandı 2012-06-14 14:21
@ 10 cevap

Algoritmanın zaman karmaşıklığı nasıl bulunur

Girişinin boyutuna bağlı olarak ne kadar makine talimatı yapacağını ekler ve ardından ifadeyi en büyüğüne basitleştirir (N çok büyük olduğunda) ve herhangi bir basitleştirici sabit faktörü içerebilir.

Örneğin, 2N + 2 makine talimatlarını sadece O(N) olarak tanımlamak için nasıl basitleştireceğinize bakalım.

Neden iki tane 2 çıkartıyoruz?

N genişledikçe algoritmanın performansıyla ilgileniyoruz.

İki üyeyi 2N ve 2 olarak düşünün.

N büyük olduğunda bu iki terimin göreceli etkisi nedir? Diyelim ki N bir milyon.

O zaman ilk terim 2 milyon, ikinci terim sadece 2.

Bu nedenle, büyük N'nin en büyük üyeleri dışındaki her şeyi atıyoruz.

Şimdi 2N + 2 gittik.

Geleneksel olarak, sadece sürekli faktörlerin performansıyla ilgileniyoruz.

Bu, N büyük olduğunda performans farkının sabit katları olup olmadığını önemsemeyeceğimiz anlamına gelir. Her durumda, önce 2N bloğu tanımlanmamıştır. Böylece, en basit ifadeye gitmek için sabit bir katsayı ile çarpabilir veya bölünebiliriz.

Böylece 2N sadece N olur N

322
14 июня '12 в 14:25 2012-06-14 14:25 Cevap, Andrew Tomazos tarafından 14 Haziran 12'de , 14:25 de 02:25 2012-06-14 14:25

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

Aşağıdaki cevap yukarıdan kopyalanmıştır (mükemmel bağlantının iflas etmesi durumunda)

Zaman karmaşıklığını hesaplamak için en yaygın ölçü, Büyük O gösterimidir.Bu, tüm sabit faktörleri ortadan kaldırır, böylece N, sonsuzluğa yaklaştığında, çalışma süresi N'ye göre tahmin edilebilir. Genel olarak, bu şekilde düşünebilirsiniz:

 statement; 

Sürekli. Talimatın uygulanma süresi N'ye göre değişmeyecektir.

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

Doğrusaldır. Döngünün çalışma süresi doğrudan N ile orantılıdır. N iki katına çıktığında, çalışma süresi de gerçekleştirilir.

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

Kuadratik. İki döngünün çalışma süresi N karesiyle orantılıdır. N iki katına çıktığında, çalışma süresi N * N ile artar.

 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. Algoritmanın çalışma süresi, N'nin 2'ye bölünebileceği sayı ile orantılıdır. Bunun nedeni, algoritmanın çalışma alanını her yinelemenin yarısına bölmesidir.

 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'dur (N). Uygulama süresi, logaritmik olan N çevrimlerinden (yinelemeli veya özyinelemeli) oluşur, bu nedenle algoritma doğrusal ve logaritmik bir kombinasyondur.

Genel olarak, her elemanın bir boyutta olduğu bir şey doğrusaldır, her elemanın iki boyutta olduğu bir şey ikinci derecedendir ve çalışma alanının bölünmesi logaritmiktir. Kübik, üstel ve karekök gibi başka Big O boyutları da var, ancak çok yaygın değiller. Büyük O tanımı, bir ölçü olan O () olarak tanımlanır. Hızlı sıralama algoritması O (N * log (N)) olarak tanımlanacaktır.

Bunların hiçbirinin en iyi, ortalama ve en kötü önlemleri dikkate almadığını lütfen unutmayın. Her birinin kendi Big O notasyonu vardır, ayrıca bunun ÇOK basitleştirilmiş bir açıklama olduğunu unutmayın. Büyük O en yaygın olanıdır, ancak gösterdiğimden daha da karmaşık. Büyük omega, küçük o ve büyük teta gibi başka özellikler de vardır. Muhtemelen bunlarla algoritma analizi dersinin dışında karşılaşmayacaksınız .;)

342
18 янв. Cevap 18 Ocak'ta verildi . 2013-01-18 13:04 13, 13:04 2013-01-18 13:04

Buradan Alınan - Algoritmanın zamansal karmaşıklığına giriş

1. Giriş

Bilgisayar bilimlerinde, bir algoritmanın zaman karmaşıklığı, giriş verisini temsil eden dizenin uzunluğunun bir fonksiyonu olarak bir algoritmayı yürütmek için geçen süreyi ölçmektedir.

2. Büyük Kayıt Hakkında

Algoritmanın zaman karmaşıklığı genellikle katsayıları ve düşük dereceli terimleri hariç tutan büyük O gösterimi kullanılarak ifade edilir. Bu şekilde ifade edildiğinde, zamansal karmaşıklığın asimptotik olarak tanımlandığı, yani Giriş sinyalinin boyutu sonsuzluğa meyillidir.

Örneğin, algoritmanın n büyüklüğündeki tüm girişlerde istenen süre 5n 3 + 3n'den fazla değilse, asimptotik zaman karmaşıklığı O (n3) olur. Bunun üzerine daha sonra.

Biraz daha örnek:

  • 1 = O (n)
  • n = O (n2)
  • log (n) = 0 (n)
  • 2 n + 1 = 0 (n)

3. O (1) sabit zaman:

Girişin boyutuna bakılmaksızın aynı zamana ihtiyaç duyması halinde algoritmanın sabit bir sürede çalıştığı söylenir.

örnekler:

  • dizi: herhangi bir öğeye erişim
  • sabit boyutlu yığın: push ve pop yöntemleri
  • sabit boyutlu kuyruk: enqueue ve dequeue yöntemleri

4. O (n) doğrusal zaman

Algoritmanın lineer zamanda çalıştığı söylenir, eğer yürütme süresi girdi büyüklüğü ile doğru orantılıysa, yani artan girdi büyüklüğü ile sürenin doğrusal olarak arttığı söylenir.

Aşağıdaki örnekleri ele alalım: aşağıda doğrusal olarak zaman karmaşıklığı O (n) olan bir eleman arıyorum.

 int find = 66; var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 }; for (int i = 0; i < numbers.Length - 1; i++) { if(find == numbers[i]) { return; } } 

Daha fazla örnek:

  • Dizi: doğrusal arama, geçiş, minimum arama, vb.
  • ArrayList: bir yöntem içerir
  • Kuyruk: bir yöntem içerir

5. O (log n) Logaritmik zaman:

Bir algoritmanın, yürütme zamanının giriş büyüklüğünün logaritması ile orantılı olması durumunda logaritmik zamanda çalıştığı söylenir.

Örnek: ikili arama

Oyun "yirmi soru" - görev aralığındaki gizli sayının değerini tahmin etmektir. Ne zaman bir tahminde bulunursanız, tahmininizin çok mu yüksek veya çok mu düşük olduğu size söylenir. Yirmi Sorular Oyunu, aralığı yarıya indirmek için tahmininizi kullanan bir strateji içermektedir. Bu, ikili arama olarak bilinen yaygın bir problem çözme yöntemine bir örnektir.

6. O (n2) ikinci dereceden zaman

Bir algoritmanın, yürütme zamanının girdi büyüklüğünün karesiyle orantılı olması durumunda ikinci dereceden yürütülmesi söylenir.

örnekler:

7. Bazı faydalı linkler

121
27 марта '14 в 16:14 2014-03-27 16:14 Cevap 27.04.07.014 tarihinde 16:14 de verilmiştir. 2014-03-27 16:14

Bu sorunun bazı iyi cevapları olmasına rağmen. Birkaç loop örneği ile burada başka bir cevap vermek istiyorum.

  • O (n) : Eğer döngü değişkenleri sabit bir değerde artar / azalırsa, Zaman Döngüsü karmaşıklığı O (n) olarak kabul edilir. Örneğin, aşağıdaki işlevler O (n) zaman karmaşıklığına sahiptir.

     // Here c is a positive integer constant for (int i = 1; i <= n; i += c) { // some O(1) expressions } for (int i = n; i > 0; i -= c) { // some O(1) expressions } 
  • O (n ^ c) : iç içe geçmiş döngülerin zaman karmaşıklığı en içteki ifadenin çalıştırılma sayısına eşittir. Örneğin, aşağıdaki örnek özetler zaman karmaşıklığına sahiptir O (n ^ 2)

     for (int i = 1; i <=n; i += c) { for (int j = 1; j <=n; j += c) { // some O(1) expressions } } for (int i = n; i > 0; i += c) { for (int j = i+1; j <=n; j += c) { // some O(1) expressions } 

    Örneğin, sıralama sıralama ve ekleme sıralama O zaman karmaşıklığına sahiptir (n ^ 2).

  • O (Logn) Zaman Eğer çevrim değişkenleri sabit bir değerle bölünür / çarpılırsa, çevrim karmaşıklığı O (Logn) olarak kabul edilir.

     for (int i = 1; i <=n; i *= c) { // some O(1) expressions } for (int i = n; i > 0; i /= c) { // some O(1) expressions } 

    Örneğin, ikili arama, zaman karmaşıklığına sahiptir (Logn).

  • O (LogLogn) Zaman Eğer bir döngü değişkeninin sabit bir değere katlanarak azaltılması / arttırılması durumunda, bir döngünün karmaşıklığı O (LogLogn) olarak kabul edilir.

     // Here c is a constant greater than 1 for (int i = 2; i <=n; i = pow(i, c)) { // some O(1) expressions } //Here fun is sqrt or cuberoot or any other constant root for (int i = n; i > 0; i = fun(i)) { // some O(1) expressions } 

Zaman karmaşıklığı analizine bir örnek

 int fun(int n) { for (int i = 1; i <= n; i++) { for (int j = 1; j < n; j += i) { // Some O(1) task } } } 

Analiz :

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

Dolayısıyla, algoritmanın toplam zaman karmaşıklığı daha yüksektir (n + n/2 + n/3 + … + n/n) , bu da n * (1/1 + 1/2 + 1/3 + … + 1/n)

Seri ile ilgili önemli olan (1/1 + 1/2 + 1/3 + … + 1/n) O (Logn) 'dır. Dolayısıyla, yukarıdaki kodun zaman karmaşıklığı O (nLogn) 'dur.


Ref: 1 2 3

81
02 нояб. cevabı 02 Kasım Zangw verilir. 2015-11-02 12:31 '15 12:31, 2015-11-02 12:31

Örneklerle zaman karmaşıklığı

1 - Temel işlemler (aritmetik, karşılaştırma, dizi elemanlarına erişim, atama): çalışma süresi her zaman sabittir O (1)

örnek:

 read(x) // O(1) a = 10; // O(1) a = 1.000.000.000.000.000.000 // O(1) 

2 - Eğer öyleyse else ifadesi: Yalnızca iki veya daha fazla olası ifadenin maksimum çalışma süresini gerçekleştirir.

örnek:

 age = read(x) // (1+1) = 2 if age < 17 then begin // 1 status = "Not allowed!"; // 1 end else begin status = "Welcome! Please come in"; // 1 visitors = visitors + 1; // 1+1 = 2 end; 

Bu nedenle, yukarıdaki sahte T kodunun karmaşıklığı (n) = 2 + 1 + maks (1, 1 + 2) = 6'dır. Dolayısıyla, büyük oh hala sabit T (n) = O (1) olarak kalır.

3 - Döngü (tekrar ederken): Bu ifadenin yürütme süresi, bu döngü içindeki işlem sayısı ile çarpılan döngü sayısıdır.

örnek:

 total = 0; // 1 for i = 1 to n do begin // (1+1)*n = 2n total = total + i; // (1+1)*n = 2n end; writeln(total); // 1 

Dolayısıyla, karmaşıklığı T (n) = 1 + 4n + 1 = 4n + 2'dir. Dolayısıyla, T (n) = O (n).

4 - İç içe döngü (döngüsel döngü): ana döngüde en az bir döngü olduğundan, bu ifadenin yürütme süresi O (n ^ 2) veya O (n ^ 3).

örnek:

 for i = 1 to n do begin // (1+1)*n = 2n for j = 1 to n do begin // (1+1)n*n = 2n^2 x = x + 1; // (1+1)n*n = 2n^2 print(x); // (n*n) = n^2 end; end; 

Toplam teslim süresi

Algoritmayı analiz ederken, toplam çalışma süresi vardır:

  • O (1) - Sabit süre Sabit süre, çalışma süresinin sabit olduğu, girişin boyutundan etkilenmediği anlamına gelir.

  • O (n) - Doğrusal zaman Algoritma n girdi boyutunu aldığında, aynı zamanda n işlemi de gerçekleştirir.

  • O (log n) - Logaritmik zaman O (log n) çalışma zamanına sahip olan algoritma, O (n) 'den biraz daha hızlıdır. Genellikle algoritma problemi aynı büyüklükteki alt bölümlere ayırır. Örnek: ikili arama algoritması, ikili dönüşüm algoritması.

  • O (n log n) - Doğrusal zaman Bu zaman, genellikle problemi alt güçlere bölen ve daha sonra bunları n kere birleştiren "ayırma ve fetih algoritmaları" nda bulunur. Örnek: Birleştirme Sıralama algoritması.

  • O (n 2 ) - Kuadratik Zaman Kabarcık sıralama algoritmasına bakın!

  • O (n 3 ) - Kübik zaman O (n 2 ) ile aynı prensibe sahiptir.

  • O (2 n ) - Üstel zaman Bu çok yavaş, çünkü n = 1000.000, T (n) 21000.000 ise girdi daha büyük olur. Brute Force algoritması bu çalışma süresine sahip.

  • O (n!) - Faktoring Zamanı ÇOK YAVAŞ !!! Örnek: satıcıyla ilgili sorun

Bu makaleden alınmıştır . Çok iyi anlatılmalı ve okumalısınız.

66
19 апр. Yanıtla Yasser 19 Nis 2014-04-19 12:36 '14 12:36, 2014-04-19 12:36

Bir kodu analiz ederken, sırayla analiz etmeniz ve her işlemi saymanız / zamanın karmaşıklığını tanımanız gerekir, sonuçta tüm resmi elde etmek için özetlemeniz gerekir.

Örneğin, doğrusal bir karmaşıklığa sahip basit bir döngünüz olabilir, ancak daha sonra aynı programda bir kübik karmaşıklığa sahip üçlü bir döngüye sahip olabilirsiniz, böylece programınız bir kübik karmaşıklığa sahip olur . Bu büyüme ilkesidir.

Algoritmanın zaman karmaşıklığının olasılıklarının ne olduğunu görelim, yukarıda bahsettiğim büyüme düzenini görebilirsiniz:

  • Sabit süre , büyüme 1 sırasıdır, örneğin: a = b + c .

  • Logaritmik zaman , LogN büyüme düzenine sahiptir, genellikle bir şeyi ikiye böldüğünüzde (ikili arama, ağaçlar, hatta döngüler) ya da bir şeyi aynı şekilde çarptığınızda olur.

  • Doğrusal , büyüme sırası N , örneğin

     int p = 0; for (int i = 1; i < N; i++) p = p + 2; 
  • Doğrusal , büyüme sırası n*logN , genellikle ayırma ve fetih algoritmalarında bulunur.

  • Kübik , büyüme sırası N^3 , klasik bir örnek, tüm üçüzleri kontrol ettiğiniz üçlü bir döngüdür:

     int x = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) x = x + 2 
  • Üstel büyüme sırası 2^N genellikle kapsamlı bir arama yaptığınızda ortaya çıkar, örneğin, belirli bir kümenin alt kümelerini kontrol edin.

36
05 июня '16 в 12:43 2016-06-05 12:43 Cevap Aleksandar Makragić tarafından 05 Haziran 'da saat 12: 43'te 2016-06-05 12:43

Kısacası, zaman karmaşıklığı, işlem sayısının veya bir algoritmanın yürütme süresinin artan girdi büyüklüğü ile nasıl büyüdüğünü özetlemenin bir yoludur.

Çoğu şey gibi, bir kokteyl de anlamamızı sağlayabilir.

O (n)

Partiye geldiğinde, herkesle el sıkışmalısın (her öğe üzerinde işlem yap). N katılımcı sayısı arttıkça, her bir elin titremesi için gereken süre / iş O(N) olarak artar.

Neden O(N) cN değil?

İnsanlarla el sıkışırken geçen sürelerde bir fark var. Bunu ortalayabilir ve sabit bir c ile sabitleyebilirsiniz. Ancak buradaki temel işlem - herkesle yapılan bir el sıkışma - c ne olduğuna bakılmaksızın her zaman O(N) ile orantılı olacaktır. Bir kokteyl partisine gitmemiz gerekip gerekmediğini tartıştığımızda, bu toplantıların neye benzediğinin en küçük detayları dışında, herkesle buluşmak zorunda kalacağımızla ilgileniyoruz.

0 (N ^ 2)

Baş kokteyl, herkesin herkesle buluştuğu aptalca bir oyun oynamanızı istiyor. Bu nedenle, diğer insanlarla tanışmalısınız ve bir sonraki insan zaten sizinle tanıştığı için N-2 tanışmalı. Bu serinin toplamı x^2/2+x/2 . Katılımcı sayısı arttıkça, x^2 terimi çok hızlı olur, bu yüzden diğer her şeyi bıraktık.

0 (N ^ 3)

Başkalarıyla tanışmalı ve her toplantıda odadaki herkes hakkında konuşmalısın.

0 (1)

Ev sahibi bir şey duyurmak istiyor. Bir bardak atıp yüksek sesle konuşuyorlar. Herkes onları duyar. Orada kaç ziyaretçi olursa olsun, bu işlem her zaman aynı miktarda zaman alır.

O (log N)

Sunucu, masadaki herkesi alfabetik sıraya göre koydu. Dan nerede? Adam ve Mandy arasında bir yerde olması gerektiğini düşünüyorsun (tabii ki, Mandy ile Zach arasında değil!). Buna bakıldığında, George ve Mandy arasında mı? Hayır. Adam ve Fred arasında ve ayrıca Cindy ve Fred arasında olmalı. Ve böylece ... kümenin yarısına ve sonra kümenin yarısına bakarak Dan'i etkili bir şekilde bulabiliriz. Sonunda, insanlara O bakarız (log_2 N) .

O (N log N)

Yukarıdaki algoritmayı kullanarak masada nerede oturulacağını bulabilirsiniz. Eğer masaya çok sayıda insan gelirse, birer birer ve herkes bunu yapardı ki bu O olacaktır (N log N) . Öyle görünüyor ki, karşılaştırılmaları gerektiğinde, herhangi bir öğe koleksiyonunu sıralama zamanı geldi.

En iyi / en kötü durum

Partiye gelip Inigo'yu bulmak zorundasın - ne kadar sürer? Ne zaman vardığına bağlı. Herkes etrafta yanıp sönerse, en kötü durumdasınız: O(N) alacaktır. Ancak, herkes masada oturuyorsa, sadece O(log N) . Ya da belki motorsiklet yarışçısının gücünü sahipler için kullanabilirsiniz ve sadece O(1) alacaktır.

Ev sahibinin uygun olmadığını varsayarak, Inigo arama algoritmasının geldiğiniz tarafın durumuna bağlı olarak daha düşük bir O(log N) ve bir üst O(N) sınırı olduğunu söyleyebiliriz.

Uzay ve iletişim

Algoritmaların uzay veya iletişimi nasıl kullandığını anlamak için aynı fikirler uygulanabilir.

Knut, Başlıkların Karmaşıklığı” başlıklı ilk başlık hakkında iyi bir makale yazdı.

Teorem 2: keyfi olarak uzun karmaşıklık şarkıları vardır O (1).

İspat: (Casey ve güneş şeridi nedeniyle). (15) ile tanımlanmış, ancak

 V_k = 'That the way,' U 'I like it, ' U U = 'uh huh,' 'uh huh' 

herkes için

29
14 окт. Cevap Richard tarafından 14 ekimde verildi . 2015-10-14 07:12 '15 07:12 2015-10-14 07:12

Bu sorunun tam tersi olduğunu biliyorum ve burada mükemmel cevaplar var, ancak yine de bu yazıya rastlayacak matematiksel düşünen insanlar için başkalarını paylaşmak istiyorum. Master teoremi , karmaşıklığı incelerken bilinmesi gereken başka bir faydalı şeydir. Başka cevaplarda bahsettiğini görmedim.

3
04 нояб. Cevap Gentian Kasa 04 Kasım'da verildi. 2015-11-04 12:20 '15 12:20 2015-11-04 12:20

O (n), bir algoritmanın zaman karmaşıklığını kaydetmek için kullanılan büyük bir gösterimdir. Bir algoritmaya yürütme sayısını eklediğinizde, 2N + 2 gibi bir ifadeye sahip olursunuz, bu ifadede N baskın terimdir (ifadesi, değeri yükselir veya azalırsa ifadede en büyük etkiye sahiptir). Şimdi O (N) zaman karmaşıklığı ve N baskın terimdir. örnek

 For i= 1 to n; j= 0; while(j<=n); j=j+1; 

burada, iç döngü için toplam uygulama sayısı n + 1'dir ve dış döngü için toplam uygulama sayısı n (n + 1) / 2'dir, dolayısıyla tüm algoritma için toplam uygulama sayısı n + 1 + n (n + 1/2) = ( n ^ 2 + 3n) / 2. Burada n ^ 2 baskın terimdir, bu nedenle bu algoritmanın zaman karmaşıklığı O (n ^ 2) 'dir.

2
11 марта '13 в 23:18 2013-03-11 23:18 Cevap 11 Mart 1313'te ifra khan tarafından 23:18 2013-03-11 23:18 tarihinde verilmiştir.

Algoritma hakkında bir fikir edinmek için, genellikle bunu deneysel olarak yapıyorum. Sadece N girişini değiştirin ve hesaplamanın ne kadar sürdüğünü görün. Bu, biraz düşünmeyi gerektirir, çünkü big-O, algoritmanın en kötü geçici karmaşıklığını tanımlar ve en kötü durumu bulmak zor olabilir.