Alqoritmin zamanın mürəkkəbliyini necə tapmaq olar

Sual

Alqoritmi zamanın mürəkkəbliyini necə tapmaq olar?

SO sualını dərc etmədən əvvəl nə etdim?

Bu , bu və bir çox digər keçidlərdən keçdim

Amma heç vaxt, vaxtın mürəkkəbliyini necə hesablamaq üçün aydın və birbaşa izahat verə biləcəyəm.

Nə bilirəm

Kodun aşağıda olduğu kimi sadədir:

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

Aşağıdakı kimi bir döngəni deyin:

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

int i = 0; Bu yalnız bir dəfə ediləcək. Vaxt həqiqətən i=0 hesablanır, bəyannamə deyil.

i <n; Bu N + 1 dəfə ediləcək.

I ++ Bu, N dəfə ediləcək.

Beləliklə, bu dövrün tələb etdiyi əməliyyatlar sayıdır

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

Qeyd Bu müvəqqəti mürəkkəbliyi hesablayarkən mənim anlayışımdan əmin deyiləm.

Nə bilmək istərdim?

Tamam, buna görə də bu kiçik əsas hesablamalar, bilirəm, bilirəm, amma çox hallarda vaxt mürəkkəbliyi gördüm

O (N), O (n2), O (log n), O (n!) .... və digərləri ,

Kimsə mənə algoritmanın zamanın mürəkkəbliyini necə hesablamağa kömək edə bilər? Əminəm ki, mənim kimi bilmək istəyən bir çox yeniliklər var.

724
14 июня '12 в 14:21 2012-06-14 14:21 Yasser 14 İyun '12 'də saat 14.1' də təyin olunub . 2012-06-14 14:21
@ 10 cavab

Alqoritmin zamanın mürəkkəbliyini necə tapmaq olar

Girişin ölçüsündən asılı olaraq nə qədər maşın talimatını işə salacaqsınız və sonra ifadə ən sadələşdirilmişdir (N olduqca böyük olduğunda) və hər hansı bir sadələşdirici sabit faktoru daxil edə bilərsiniz.

Məsələn, yalnız O(N) kimi təsvir etmək üçün 2N + 2 maşın təlimatlarını necə asanlaşdırdığına baxaq.

Niyə iki ikisini çıxarırıq?

N böyük olduğunda alqoritm performansını maraqlandırırıq.

2N və 2 üzvünü nəzərdən keçirin.

N olduqca böyüdükdə bu iki şərtin nisbi təsiri nədir? N saylı bir milyon olduğunu düşünün.

Sonra birinci dövr 2 milyon, ikincisi isə yalnız 2dir.

Bu səbəbdən böyük nəhənglər üçün ən böyük üzvlərdən başqa hər şeyi atırıq.

İndi biz 2N + 2 dən 2N ə 2N .

Ənənəvi olaraq, biz yalnız faktorları yerinə yetirməklə maraqlanırıq.

Bu, n böyük olduğunda performans fərqinin hər hansı bir sabit kvadratının olmadığını düşünməməyimiz deməkdir. Hər halda, 2N bloku ilk olaraq müəyyən edilmir. Beləliklə, biz sadə ifadəyə getmək üçün sabit əmsalla çarpar və ya bölmək olar.

Beləliklə, 2N yalnız N olur.

322
14 июня '12 в 14:25 2012-06-14 14:25 Cavab Andrew Tomazos tərəfindən 14 İyun 'da saat 14:25' də verilir. 2012-06-14 14:25

Bu gözəl bir məqalə: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

Aşağıdakı cavab yuxarıdan kopyalanır (mükəmməl link iflas etdiyi halda)

Temporal mürəkkəbliyi hesablamaq üçün ən ümumi metrik Böyük O qeydidir və bu, bütün sabit faktorları aradan qaldırır, belə ki, N nöqteyi-nəzərdən sonsuzluğa yaxınlaşdıqda işləmə vaxtı N-ə görə hesablana bilər. Ümumiyyətlə, bu şəkildə düşünə bilərsiniz:

 statement; 

Daimi. Təlimatın yerinə yetirilməsi müddəti N. ilə bağlı dəyişməyəcəkdir.

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

Doğrudur. Döngünün işləmə müddəti N. ilə nisbətən mütənasibdir. N ikiqat olduqda, işləmə vaxtı da yerinə yetirilir.

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

Kvadratik. İki döngənin işləmə vaxtı N kvadratına mütənasibdir. N ikiqat olduqda, N * N

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

Logarithmically. Alqoritmanın işləmə vaxtı N-ə bölünməyə imkan verən dəfə sayına nisbətlidir. Bu, alqoritm iş yerini hər bir təkrarlama ilə yarıya bölü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). İcra zamanı logaritmik olan N dövründən (yineleyici və təkrarlayıcı) ibarətdir, beləliklə, alqoritm linear və logaritmik birləşməsidir.

Ümumiyyətlə, bir ölçüdə hər bir elementlə bir şey xətti olur, iki ölçüdə hər bir elementlə bir şey kvadratdır və iş sahəsinin bölünməsi yarısı logaritmikdir. Kub, eksponent və kvadrat kök kimi digər Big O ölçüləri var, lakin onlar bu qədər çox deyil. Böyük O ifadəsi O () kimi təsvir olunur, burada bir tədbirdir. Sürətli sort alqoritmi O (N * log (N)) kimi təsvir olunacaq.

Xahiş edirik, bunlardan heç biri ən yaxşı, ortalama və ən pis tədbirləri nəzərə alır. Hər bir öz Big O qeydinə malikdir və qeyd etmək lazımdır ki, bu, çox sadələşdirilmiş izahdır. Big O ən çox yayılmışdır, amma göstərdiyimdən daha mürəkkəbdir. Böyük omega, kiçik o və böyük teta kimi digər təsvirlər var. Yəqin ki, onları alqoritm təhlilləri xaricində qarşılamırsınız .;)

342
18 янв. cavab Achow 18 yanvar verilir . 2013-01-18 13:04 '13 at 13:04 2013-01-18 13:04

Buradan götürülmüş - Alqoritmin müvəqqəti mürəkkəbliyinə giriş

1. Giriş

Kompüter elmində bir alqoritmanın zamanın mürəkkəbliyi giriş məlumatlarını təmsil edən simli uzunluğunun bir funksiyası kimi bir alqoritmi icra etmək üçün lazım olan miqdarını müəyyənləşdirir.

2. Record haqqında böyük

Alqoritmlərin vaxt mürəkkəbliyi, adətən, aşağı səviyyəli əmsalları və şərtləri istisna edən böyük O notation ilə ifadə edilir. Bu şəkildə ifadə edildiyi zaman, temporal mürəkkəbliyin asimptotik olaraq təsvir edildiyi, yəni. Giriş sinyalinin ölçüsü sonsuzluğa meyllidir.

Məsələn, n ölçüsünün bütün girişlərində alqoritm tələb olunan vaxt 5n 3 + 3n-dən çox deyilsə, asimptotik vaxt mürəkkəbliyi O (n 3 ) dir. Bundan sonra daha çox.

Bəzi nümunələr:

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

3. O (1) sabit vaxt:

Alqoritm girişin ölçüsündən asılı olmayaraq eyni vaxt tələb etməsi halında sabit bir vaxtda işlədildiyi deyilir.

Nümunələr:

  • array: hər hansı elementə giriş
  • sabit ölçülü yığın: push və pop üsulları
  • sabit ölçülü sıra: enqueue və dequeue metodları

4. O (n) xətti vaxt

Alqoritm xətti vaxtda işləyir, əgər onun icra müddəti girişin ölçüsüylə, yəni artan giriş ölçüsündə doğrusal olaraq artırsa, işlədilir.

Aşağıdakı nümunələri nəzərdən keçirin: aşağıda mən linearly O (n) zaman mürəkkəbliyi olan bir element axtarıram.

 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 çox nümunə:

  • Dizi: lineer axtarış, traversal, minimum axtarış və s.
  • ArrayList: bir metodu ehtiva edir
  • Queue: bir üsul ehtiva edir

5. O (log n) Logaritmik vaxt:

Bir alqoritm logaritmik vaxtda işlədiyi zaman, onun icra müddəti giriş ölçüsünün logarithminə mütənasibdir.

Misal: ikili axtarış

Oyunun "yirmi sual" sözünü yadda saxla - vəzifə aralıqdakı gizli nömrənin dəyərini təxmin edir. Hər tahmin etdiyiniz zaman, tahmininiz çox yüksək və ya çox aşağı olub-olmadığını deyirsiniz. Yeddi Sorğu Oyunu, aralıq sayını yarıya endirmək üçün təxminlərinizi istifadə edən bir strategiyadır. Bu ikili axtarış kimi tanınan ümumi bir problem həll metoduna nümunədir.

6. O (n2) kvadratik vaxt

İcra vaxtının giriş ölçüsünün kvadratına mütənasib olması halında bir alqoritm kvadratik müddətdə icra edilir.

Nümunələr:

7. Bəzi faydalı bağlantılar

121
27 марта '14 в 16:14 2014-03-27 16:14 Cavab Yasser tərəfindən 27 Mart '14 'də 16:14' də veriləcək 2014-03-27 16:14

Bu suallara bir neçə yaxşı cavab olsa da. Buraya bir neçə nümunə ilə bir cavab vermək istərdim.

  • O (n) : Döngü dəyişənləri sabit dəyərlə artırsa / azalırsa, zaman dövrü mürəkkəbliyi O (n) kimi qəbul edilir. Məsələn, aşağıdakı funksiyalar O (n) zaman mürəkkəbliyinə malikdir.

     // 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) : Daxili döngələrin vaxtın mürəkkəbliyi ən kiçik bəyanatın yerinə yetirilməsinin sayına bərabərdir. Məsələn, aşağıdakı nümunə təsvirləri 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 } 

    Məsələn, çeşidlənməsi və sıralama sıralamasının O vaxt mürəkkəbliyi var (n ^ 2).

  • O (Logn) Vaxt Döngü dəyişənləri sabit bir dəyər ilə bölünür / çarpıldıqda dövrü mürəkkəbliyi O (Logn) hesab olunur.

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

    Məsələn, ikili axtarışda vaxt mürəkkəbliyi O (Logn) var.

  • O (LogLogn) Vaxt Döngü dəyişənləri sabit bir dəyər ilə xarakterik olaraq azaldılır / artdıqda bir dövrünün mürəkkəbliyi O (LogLogn) kimi qəbul 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 mürəkkəbliyi analizinin bir nümunəsi

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

Təhlil :

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.

Beləliklə, alqoritmlərin ümumi mürəkkəbliyi (n + n/2 + n/3 + … + n/n) , n * (1/1 + 1/2 + 1/3 + … + 1/n)

Serial (1/1 + 1/2 + 1/3 + … + 1/n) haqqında əhəmiyyətli olan O (Logn). Beləliklə, yuxarıda göstərilən kodun vaxt mürəkkəbliyi O (nLogn).


Ref: 1 2 3

81
02 нояб. cavab zangw 02 noyabr. 2015-11-02 12:31 '15 at 12:31 pm 2015-11-02 12:31

Misallarla vaxt mürəkkəbliyi

1 - Əsas əməliyyatlar (aritmetik, müqayisə, serial elementlərinə giriş, tapşırıq): əməliyyat saatı hər zaman sabitdir (1)

Məsələn:

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

2 - Əgər başqa ifadələr varsa: Yalnız iki və ya daha çox mümkün ifadələrin maksimum işləmə vaxtını yerinə yetirir.

Məsələn:

 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; 

Beləliklə, yuxarıdakı pseudocode T (n) = 2 + 1 + max (1, 1 + 2) = 6 mürəkkəbliyi. Beləliklə, böyük oh hələ də sabit T (n) = O (1) olaraq qalır.

3 - Looping (for, while, repeat): Bu bəyanatın yerinə yetirmə müddəti bu dövrü içərisində olan əməliyyatlar sayına çarpan sayının sayıdır.

Məsələn:

 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 

Beləliklə, onun mürəkkəbliyi T (n) = 1 + 4n + 1 = 4n + 2 olur. Beləliklə, T (n) = O (n).

4 - Nested loop (цикл loop): əsas loopda ən azı bir loop olduğundan, bu ifadənin icra müddəti O (n ^ 2) və ya O (n ^ 3).

Məsələn:

 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; 

Ümumi vaxt

Alqoritmi təhlil edərkən, ümumi işləmə müddəti var:

  • O (1) - Sabit vaxt Sabit vaxt işləmə müddəti sabit olduğundan, girişin ölçüsündən asılı deyildir.

  • O (n) - xətti vaxt alqoritm n daxiletmə ölçüsünü alırsa, n əməliyyatları da yerinə yetirir.

  • O (log n) - Logarithmic vaxt O (log n) işləyən vaxt alqoritmi O (n) -dən bir az daha sürətlidır. Adətən alqoritm problemi eyni ölçülü alt bölmələrə bölür. Məsələn: ikili axtarış alqoritmi, ikili dönüşüm alqoritmi.

  • O (n log n) - Doğrusal vaxt Bu dəfə tez-tez "ayrılıq və fəth alqoritmləri" də yer alır, bu da problemi sub-səlahiyyətlərə təkrarlayır və sonra n dəfə birləşdirir. Misal: Sort alqoritmini birləşdirin.

  • O (n 2 ) - Kvadratik vaxt Bubble sorting alqoritmasına baxın!

  • O (n 3 ) - Kübik vaxt O (n 2 ) ilə eyni prinsipə malikdir.

  • O (2 n ) - Üstün vaxt Bu çox yavaşdır, çünki n = 1000.000, T (n) 21000.000 olduqda, giriş daha böyük olur. Brute Force alqoritminin bu işləmə müddəti var.

  • O (n!) - Faktorial vaxt ən çox YÜKLƏ! Məsələn: satıcının problemi (tsp)

Bu məqalədən götürülmüşdür. Çox yaxşı izah oxumaq lazımdır.

66
19 апр. Cavab Yasser Apr 19 2014-04-19 12:36 '14 da 12:36 2014-04-19 12:36

Bir kod təhlil edərkən, hər bir əməliyyatı hesablayaraq zamanın mürəkkəbliyini tanıyaraq, onu təhlil etməli, nəticədə, bütün şəkilləri əldə etmək üçün onu yekunlaşdırmalısınız.

Məsələn, xətti bir mürəkkəbliyi olan bir sadə dövrə malik olursunuz, ancaq eyni proqramda bir kub mürəkkəbliyi ilə üçqat dövrü ola bilərsiniz, buna görə proqramınız kub mürəkkəbliyə sahib olacaq. Bu böyümə prinsipidir.

Alqoritmin zamanın mürəkkəbliyinin imkanlarını nəzərdən keçirək, yuxarıda qeyd etdiyim böyümə qaydasını görə bilərsiniz:

  • Sabit vaxt böyümə sırasına 1 , məsələn: a = b + c .

  • Logaritmik vaxt LogN artımının LogN , adətən yarı yarıya (ikili axtarış, ağaclar, hətta döngələr) ayırmaq və ya eyni şəkildə bir şey artırmaq olar.

  • Lineer , böyümə nişanı N , məsələn

     int p = 0; for (int i = 1; i < N; i++) p = p + 2; 
  • Doğrusal , böyümə qaydası n*logN , adətən, ayrılma və fəth alqoritmlərində tapılmışdır.

  • Kübik , böyümə nişanı N^3 , klassik bir nümunə, üçlü dövrdür, bütün üçlükləri yoxlayın:

     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 
  • Ekspensiv artım əmri 2^N , məsələn, müəyyən bir dəstənin alt kümelerini yoxlamaq üçün geniş axtarış apararkən baş verir.

36
05 июня '16 в 12:43 2016-06-05 12:43 Cavab Aleksandar Makragić tərəfindən 05 İyun '16' da saat 12:43 'də veriləcək 2016-06-05 12:43

Bir sözlə, zamanın mürəkkəbliyi bir alqoritmanın əməliyyat sayı və ya icra müddətinin artan giriş ölçüsünün necə artırıldığını cəmləşdirmək üçün bir yoldur.

Çox şeylər kimi, bir kokteyl bizi anlamağa kömək edə bilər.

O (n)

Partiyaya gəldikdə, hər kəslə əllərinizi sarsıtmaq lazımdır (hər bir maddə üzrə əməliyyat aparmaq lazımdır). N iştirakçılarının sayı artdıqca, hər əlini titrəmək üçün lazım olan vaxt / iş O(N) kimi artır.

Niyə O(N) deyil, cN ?

İnsanlarla əllərini sarsıtmaq üçün lazım olan müddətdə fərq var. Siz onu orta hesabla düzəldə bilərsiniz və sabit bir şəkildə düzəldə bilərsiniz. Ancaq burada əsas əməliyyat - hər kəslə bir sarsıntı - həmişə nə olursa olsun O(N) ilə mütənasib olacaq. Bir kokteyl partiyasına getməli olub-olmadığını müzakirə edərkən, biz tez-tez hər kəslə görüşmək məcburiyyətindəyik, bu yığıncaqların nə qədər kiçik detalları istisna olmaqla.

O (N ^ 2)

Qurğuşun kokteyli hər kəsin hər kəslə görüşdüyü bir oyun oynayır. Buna görə də, digər insanlarla tanış olmalı və növbəti şəxs artıq görüşmüşdür, çünki onlar N-2 tanış olmalıdırlar və s. Bu seriyanın cəmi x^2/2+x/2 . Iştirakçıların sayı artdıqca x^2 terməsi çox sürətli olur, buna görə də hər şeyi tamamilə buraxırıq.

O (N ^ 3)

Hər kəslə görüşməlisiniz və hər bir görüşdə odadakı hər kəsdən danışmalısınız.

O (1)

Ev sahibi bir şey elan etmək istəyir. Bir şüşə atırlar və səslənirlər. Hər kəs onları eşidir. Görünür, nə qədər ziyarətçi olmağına baxmayaraq, bu əməliyyat həmişə eyni vaxtda olur.

O (giriş N)

Təqdimatçı masanı hərfləri əlifba sırası ilə qoydu. Dan nerede? O, Adəm və Mandy arasında (əlbəttə, Mandy və Zach arasında deyil) bir yerdə olmağı düşünür. Bunu nəzərə alaraq, Corc və Mandy arasında mı? Xeyr O, Adəmlə Fred arasındakı, Cindy ilə Fred arasında olmalıdır. Və buna görə də ... effektiv olaraq Danı yarısını və sonra yarımın yarısını baxaraq tapa bilərik. Nəticədə, O (log_2 N) xalqına baxırıq .

O (N log N)

Yuxarıda göstərilən alqoritmi istifadə edərək masada oturmağı tapa bilərsiniz. Çox sayda adam masaya gəldiyində, bir dəfə və hər kəs bunu etdi, O (N log N) olardı. Göründüyü kimi, onlar müqayisə etmək lazımdırsa, hər hansı bir əşyaların toplanması üçün lazım olan vaxtdır.

Ən yaxşı / pis vəziyyət

Partiyaya gəlir və İnigo tapmaq lazımdır - nə qədər vaxt aparacaq? Bu gəldiyin vaxtdan asılıdır. Hər kəs ətrafında işıq saçırsa, ən pis vəziyyətdədirsiniz: O(N) alacaq. Ancaq hər kəs masada otursa, yalnız O(log N) alır. Və ya bəlkə motosiklet racer sahibləri üçün istifadə edə bilərsiniz və yalnız O(1) .

Ev sahibinin mövcud olmadığını nəzərə alsaq, İnigo axtarış alqoritminin gəldikdə partiyanın vəziyyətindən asılı olaraq daha aşağı O(log N) sərhədi və yuxarı O(N) sərhədinə malik olduğunu söyləyə bilərik.

Space və kommunikasiya

Alqoritmlərin yer və ya ünsiyyətdən necə istifadə etdiyini anlamaq üçün eyni fikirlər tətbiq edilə bilər.

Knut "Mahnı mürəkkəbliyi" adlı ilk başlığı ilə yaxşı bir yazı yazdı.

Teoremi 2: O (1) mürəkkəbliyi uzunmüddətli uzun mahnılar var.

Proof: (Casey və günəş şeridi səbəbindən). Sk mahnılarının (15) ilə təyin etdiyi düşünün, ancaq

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

bütün k üçün.

29
14 окт. 14 oktyabrda Richard tərəfindən verilmiş cavab 2015-10-14 07:12 '15 at 7:12 'də 2015-10-14 07:12

Bilirəm ki, bu sual tərsinə çevrilir və buradakı əla cavablar var, amma bu vəzifədə büdrəyəcək riyazi düşüncəli insanlar üçün başqaları ilə bölüşmək istərdim. Master teoremi , mürəkkəbliyi öyrənərkən bilmək üçün başqa faydalı bir şeydir. Mən digər cavablarda qeyd etdiyimi görmədim.

3
04 нояб. cavab Gentian Kasa verildi 04 Noyabr. 2015-11-04 12:20 '15 'da saat 12:20' de

O (n) bir alqoritmin vaxtın mürəkkəbliyini qeyd etmək üçün istifadə edilən böyük bir qeyddir. Bir alqoritmdə edamların sayını əlavə etdikdə, 2N + 2 kimi bir ifadəni alırsınız, N ifadəsindəki dominant müddəti (dəyəri dəyərinin artması və ya azalması halında ifası ən böyük təsir göstərir). İndi O (N) zamanın mürəkkəbliyi, N isə dominantdır. Misal

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

daxili loop üçün edamların ümumi sayı n + 1dir və xarici loop üçün edamların ümumi sayı n (n + 1) / 2dir, buna görə bütün alqoritmlərin ümumi sayı n + 1 + n (n + 1/2) = ( n ^ 2 + 3n) / 2. burada n ^ 2 dominant bir dövrdür, buna görə də bu alqoritmlərin vaxt mürəkkəbliyi O (n ^ 2)

2
11 марта '13 в 23:18 2013-03-11 23:18 cavab 11 mart '13 'də saat 23:18' də ifra xan tərəfindən verilmişdir 2013-03-11 23:18

Alqoritm haqqında fikir almaq üçün, mən tez-tez bu təcrübəni edim. Yalnızca N girişini dəyişdirin və hesablamanın nə qədər davam etdiyini görürük. Bu, bəzi fikirləri tələb edir, çünki böyük-O alqoritm ən pis temporal mürəkkəbliyi təsvir və ən pis halda tapmaq çətin ola bilər.

Для этого теоретически ваш подход кажется мне правдивым: пройдитесь по программе (всегда выбирайте самый сложный путь), добавляйте индивидуализированные времена и избавляйтесь от всех констант/факторов. Вложенные петли, прыжки и т.д. Могут сделать это довольно сложным, но я не могу думать о серебряной пуле, чтобы решить это в противном случае.

Вы также можете быть проиндексированы в http://en.wikipedia.org/wiki/Big_O_notation , несмотря на то, что он довольно математичен.

Я также нашел http://en.wikipedia.org/wiki/Analysis_of_algorithms

-6
ответ дан stefanl 14 июня '12 в 14:49 2012-06-14 14:49

Другие вопросы по меткам или Задайте вопрос