Bagaimana menemukan kompleksitas waktu suatu algoritma

Pertanyaan

Bagaimana menemukan kompleksitas waktu suatu algoritma?

Apa yang telah saya lakukan sebelum memposting pertanyaan di SO?

Saya telah melalui ini , ini dan banyak tautan lainnya

Tetapi tidak ada tempat saya dapat menemukan penjelasan yang jelas dan langsung ke depan untuk bagaimana menghitung kompleksitas waktu.

Apa yang aku tahu ?

Ucapkan kode sesederhana yang di bawah ini:

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

Katakan untuk loop seperti di bawah ini:

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

int i = 0; Ini akan dieksekusi hanya sekali . Waktu sebenarnya dihitung i=0dan bukan deklarasi.

i <N; Ini akan dieksekusi N + 1 kali

i ++; Ini akan dieksekusi N kali

Jadi jumlah operasi yang dibutuhkan oleh loop ini adalah

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

Catatan: Ini mungkin masih salah, karena saya tidak yakin dengan pemahaman saya tentang penghitungan kompleksitas waktu

Apa yang ingin saya ketahui?

Ok, jadi kalkulasi dasar kecil ini saya rasa saya tahu, tetapi dalam kebanyakan kasus saya telah melihat kompleksitas waktu sebagai

O (N), O (n2), O (log n), O (n!) .... dan banyak lainnya ,

Adakah yang bisa membantu saya memahami bagaimana cara menghitung kompleksitas waktu suatu algoritma? Saya yakin ada banyak pemula seperti saya yang ingin tahu ini.

Bagaimana menemukan kompleksitas waktu suatu algoritma

Anda menjumlahkan berapa banyak instruksi mesin yang akan dieksekusi sebagai fungsi dari ukuran inputnya, dan kemudian menyederhanakan ekspresi ke istilah terbesar (ketika N sangat besar) dan dapat mencakup faktor konstan penyederhanaan.

Misalnya, mari kita lihat bagaimana kami menyederhanakan 2N + 2instruksi mesin untuk menggambarkan ini sebagai adil O(N).

Mengapa kita menghapus keduanya 2?

Kami tertarik pada kinerja algoritma karena N menjadi besar.

Pertimbangkan dua istilah 2N dan 2.

Apa pengaruh relatif kedua istilah ini karena N menjadi besar? Misalkan N adalah sejuta.

Kemudian suku pertama adalah 2 juta dan suku kedua hanya 2.

Karena alasan ini, kami menjatuhkan semua kecuali persyaratan terbesar untuk N. besar

Jadi, sekarang kami telah pergi dari 2N + 2ke 2N.

Secara tradisional, kami hanya tertarik pada kinerja hingga faktor konstan .

Ini berarti bahwa kami tidak benar-benar peduli jika ada beberapa perbedaan kinerja yang konstan ketika N besar Unit 2N tidak terdefinisi dengan baik sejak awal. Jadi kita dapat mengalikan atau membagi dengan faktor konstan untuk mendapatkan ekspresi paling sederhana.

Jadi 2Nmenjadi adil N.

Ini adalah artikel yang bagus: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

Jawaban di bawah ini disalin dari atas (jika tautan bagus rusak)

Metrik yang paling umum untuk menghitung kompleksitas waktu adalah notasi O Besar. Ini menghapus semua faktor konstan sehingga waktu berjalan dapat diperkirakan dalam kaitannya dengan N saat N mendekati tak terhingga. Secara umum Anda bisa memikirkannya seperti ini:

statement;

Konstan. Waktu berjalan pernyataan tidak akan berubah sehubungan dengan N.

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

Linier. Waktu berjalan dari loop berbanding lurus dengan N. Saat N berlipat ganda, demikian juga waktu berjalan.

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

Apakah kuadratik. Waktu berjalan dari dua loop sebanding dengan kuadrat N. Ketika N berlipat ganda, waktu berjalan meningkat sebesar 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;
}

Apakah logaritmik. Waktu berjalan dari algoritma sebanding dengan berapa kali N dapat dibagi dengan 2. Ini karena algoritma membagi area kerja menjadi setengah dengan setiap iterasi.

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

Apakah N * log (N). Waktu berjalan terdiri dari N loop (iteratif atau rekursif) yang bersifat logaritmik, sehingga algoritma ini merupakan kombinasi linear dan logaritmik.

Secara umum, melakukan sesuatu dengan setiap item dalam satu dimensi adalah linier, melakukan sesuatu dengan setiap item dalam dua dimensi adalah kuadratik, dan membagi area kerja menjadi setengahnya adalah logaritmik. Ada ukuran Big O lainnya seperti kubik, eksponensial, dan akar kuadrat, tetapi mereka hampir tidak umum. Notasi O besar digambarkan sebagai di O ( <type> )mana <type>ukurannya. Algoritme quicksort akan digambarkan sebagai O ( N * log ( N ) ).

Perhatikan bahwa tidak satu pun dari ini telah memperhitungkan ukuran kasus terbaik, rata-rata, dan terburuk. Masing-masing akan memiliki notasi Big O sendiri. Perhatikan juga bahwa ini adalah penjelasan yang SANGAT sederhana. Big O adalah yang paling umum, tetapi juga lebih kompleks yang saya tunjukkan. Ada juga notasi lain seperti omega besar, o kecil, dan theta besar. Anda mungkin tidak akan menjumpai mereka di luar kursus analisis algoritma. ;)

Diambil dari sini - Pengantar Kompleksitas Waktu dari Algoritma

1. Perkenalan

Dalam ilmu komputer, kompleksitas waktu dari suatu algoritma mengkuantifikasi jumlah waktu yang diambil oleh suatu algoritma untuk dijalankan sebagai fungsi dari panjang string yang mewakili input.

2. Notasi O besar

Kompleksitas waktu dari suatu algoritma umumnya dinyatakan menggunakan notasi O besar, yang mengecualikan koefisien dan istilah urutan yang lebih rendah. Ketika diekspresikan dengan cara ini, kompleksitas waktu dikatakan dideskripsikan secara asimptot, yaitu, ketika ukuran input mencapai tak terhingga.

Misalnya, jika waktu yang dibutuhkan oleh suatu algoritma pada semua input ukuran n paling banyak 5n ³ + 3n, kompleksitas waktu asimptotik adalah O (n ³ ). Lebih lanjut tentang itu nanti.

Beberapa contoh lagi:

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

3. O (1) Waktu Konstan:

Algoritma dikatakan berjalan dalam waktu konstan jika membutuhkan jumlah waktu yang sama terlepas dari ukuran input.

Contoh:

• array: mengakses elemen apa saja
• tumpukan ukuran tetap: metode push dan pop
• antrian ukuran tetap: metode enqueue dan dequeue

4. O (n) Waktu Linear

Algoritma dikatakan berjalan dalam waktu linier jika eksekusi waktunya berbanding lurus dengan ukuran input, yaitu waktu tumbuh secara linier ketika ukuran input meningkat.

Perhatikan contoh-contoh berikut, di bawah ini saya mencari elemen secara linear, ini memiliki kompleksitas waktu O (n).

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;
    }
}

Lebih banyak contoh:

• Array: Pencarian Linear, Traversing, Cari minimum dll
• ArrayList: berisi metode
• Antrian: berisi metode

5. O (log n) Waktu Logaritmik:

Algoritma dikatakan berjalan dalam waktu logaritmik jika eksekusi waktunya sebanding dengan logaritma ukuran input.

Contoh: Pencarian Biner

Ingat permainan "dua puluh pertanyaan" - tugasnya adalah menebak nilai angka tersembunyi dalam suatu interval. Setiap kali Anda membuat tebakan, Anda diberi tahu apakah tebakan Anda terlalu tinggi atau terlalu rendah. Game dua puluh pertanyaan menyiratkan strategi yang menggunakan nomor perkiraan Anda untuk membagi dua ukuran interval. Ini adalah contoh dari metode penyelesaian masalah umum yang dikenal sebagai pencarian biner

6. O (n ² ) Waktu Kuadratik

Algoritma dikatakan berjalan dalam waktu kuadrat jika eksekusi waktunya sebanding dengan kuadrat ukuran input.

Contoh:

• Sortir Bubble
• Sortir Pilihan
• Penyisipan Sortir

7. Beberapa tautan bermanfaat

• Kesalahpahaman Big-O
• Menentukan Kompleksitas Algoritma
• Lembar Curang Besar O

Meskipun ada beberapa jawaban bagus untuk pertanyaan ini. Saya ingin memberikan jawaban lain di sini dengan beberapa contoh loop.

• O (n) : Kompleksitas Waktu dari sebuah loop dianggap sebagai O (n) jika variabel loop bertambah / dikurangi dengan jumlah yang konstan. Misalnya fungsi berikut memiliki kompleksitas waktu O (n) .

  // 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) : Kompleksitas waktu loop bersarang sama dengan berapa kali pernyataan terdalam dieksekusi. Misalnya loop sampel berikut memiliki kompleksitas waktu 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
  }
  

  Misalnya, Seleksi pemilihan dan Urutan Penyisipan memiliki kompleksitas waktu O (n ^ 2) .

• O (Logn) Kompleksitas Waktu dari loop dianggap sebagai O (Logn) jika variabel loop dibagi / dikalikan dengan jumlah yang konstan.

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

  Misalnya Binary Search memiliki kompleksitas waktu O (Logn) .

• O (LogLogn) Kompleksitas Waktu dari loop dianggap sebagai O (LogLogn) jika variabel loop dikurangi / ditingkatkan secara eksponensial dengan jumlah yang konstan.

  // 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
  }
  

Salah satu contoh analisis kompleksitas waktu

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

Analisis :

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.

Jadi kompleksitas waktu total dari algoritma di atas adalah (n + n/2 + n/3 + … + n/n), Yang menjadin * (1/1 + 1/2 + 1/3 + … + 1/n)

Yang penting tentang seri (1/1 + 1/2 + 1/3 + … + 1/n)sama dengan O (Logn) . Jadi kompleksitas waktu dari kode di atas adalah O (nLogn) .

Ref: 1 2 3

Kompleksitas waktu dengan contoh-contoh

1 - Operasi Dasar (aritmatika, perbandingan, mengakses elemen-elemen array, tugas): Waktu berjalan selalu konstan O (1)

Contoh:

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

2 - If then else statement: Hanya mengambil waktu berjalan maksimum dari dua atau lebih pernyataan yang mungkin.

Contoh:

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;

Jadi, kompleksitas kode pseudo di atas adalah T (n) = 2 + 1 + maks (1, 1 + 2) = 6. Dengan demikian, besar oh masih konstan T (n) = O (1).

3 - Looping (untuk, sementara, ulangi): Waktu berjalan untuk pernyataan ini adalah jumlah perulangan dikalikan dengan jumlah operasi di dalam perulangan itu.

Contoh:

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

Jadi, kompleksitasnya adalah T (n) = 1 + 4n + 1 = 4n + 2. Jadi, T (n) = O (n).

4 - Nested Loop (looping inside looping): Karena setidaknya ada satu looping di dalam looping utama, waktu berjalan dari pernyataan ini menggunakan O (n ^ 2) atau O (n ^ 3).

Contoh:

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;

Waktu Berlari Umum

Ada beberapa waktu berjalan umum ketika menganalisis suatu algoritma:

1. O (1) - Waktu Konstan Waktu konstan berarti waktu berjalan konstan, tidak terpengaruh oleh ukuran input .

2. O (n) - Waktu Linear Ketika suatu algoritma menerima ukuran input n, itu akan melakukan operasi n juga.

3. O (log n) - Algoritma Waktu Logaritmik yang memiliki waktu berjalan O (log n) sedikit lebih cepat daripada O (n). Secara umum, algoritma membagi masalah menjadi sub masalah dengan ukuran yang sama. Contoh: algoritma pencarian biner, algoritma konversi biner.

4. O (n log n) - Waktu Linearitmik Waktu yang berjalan ini sering ditemukan dalam "algoritma pembagian & taklukkan" yang membagi masalah menjadi sub masalah secara rekursif dan kemudian menggabungkannya dalam waktu. Contoh: Algoritma Gabung Sortir.

5. O (n ² ) - Algoritma Sortir Gelembung Urut Waktu Quadratic Time!

6. O (n ³ ) - Waktu Kubik Ia memiliki prinsip yang sama dengan O (n ² ).

7. O (2 ⁿ ) - Waktu Eksponensial Sangat lambat karena input bertambah besar, jika n = 1000.000, T (n) adalah 21000.000. Algoritma Brute Force memiliki waktu berjalan ini.

8. O (n!) - Waktu faktor TERLALU !!! Contoh: Travel Salesman Problem (TSP)

Diambil dari artikel ini . Sangat jelas menjelaskan harus membaca.

Ketika Anda menganalisis kode, Anda harus menganalisisnya baris demi baris, menghitung setiap operasi / mengenali kompleksitas waktu, pada akhirnya, Anda harus menjumlahkannya untuk mendapatkan gambaran keseluruhan.

Misalnya, Anda dapat memiliki satu loop sederhana dengan kompleksitas linier , tetapi kemudian dalam program yang sama Anda dapat memiliki loop tiga yang memiliki kompleksitas kubik , sehingga program Anda akan memiliki kompleksitas kubik . Urutan fungsi pertumbuhan mulai berlaku di sini.

Mari kita lihat apa kemungkinan kompleksitas waktu dari suatu algoritma, Anda dapat melihat urutan pertumbuhan yang saya sebutkan di atas:

• Waktu yang konstan memiliki urutan pertumbuhan1, misalnya:a = b + c.

• Waktu logaritmik memiliki urutan pertumbuhanLogN, biasanya terjadi ketika Anda membagi sesuatu menjadi dua (pencarian biner, pohon, bahkan loop), atau mengalikan sesuatu dengan cara yang sama.

• Linear , urutan pertumbuhanN, misalnya

  int p = 0;
  for (int i = 1; i < N; i++)
    p = p + 2;
  

• Linearitmik , urutan pertumbuhannyan*logN, biasanya terjadi pada algoritma divide and conquer.

• Kubik , urutan pertumbuhanN^3, contoh klasik adalah loop tiga tempat Anda memeriksa semua kembar tiga:

  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
  

• Eksponensial , urutan pertumbuhan2^N, biasanya terjadi ketika Anda melakukan pencarian lengkap, misalnya memeriksa himpunan bagian dari beberapa set.

Secara longgar, kompleksitas waktu adalah cara meringkas bagaimana jumlah operasi atau run-time dari suatu algoritma bertambah ketika ukuran input bertambah.

Seperti kebanyakan hal dalam hidup, pesta koktail dapat membantu kita memahami.

DI)

Ketika Anda tiba di pesta, Anda harus menjabat tangan semua orang (melakukan operasi pada setiap item). Karena jumlah peserta Nmeningkat, waktu / pekerjaan yang Anda perlukan untuk menjabat tangan semua orang akan bertambah O(N).

Kenapa O(N)dan tidak cN?

Ada variasi dalam jumlah waktu yang diperlukan untuk berjabatan tangan dengan orang-orang. Anda bisa meratakan ini dan menangkapnya dalam konstanta c. Tetapi operasi mendasar di sini --- berjabat tangan dengan semua orang --- akan selalu proporsional dengan O(N), tidak peduli apa citu. Ketika memperdebatkan apakah kita harus pergi ke pesta koktail, kita sering lebih tertarik pada kenyataan bahwa kita harus bertemu semua orang daripada detail menit seperti apa pertemuan itu.

O (N ^ 2)

Tuan rumah pesta koktail ingin Anda memainkan permainan konyol di mana semua orang bertemu orang lain. Karena itu, Anda harus bertemu N-1orang lain dan, karena orang berikutnya sudah bertemu Anda, mereka harus bertemu N-2orang lain, dan seterusnya. Jumlah dari seri ini adalah x^2/2+x/2. Dengan bertambahnya jumlah peserta, x^2istilah menjadi besar dengan cepat , jadi kami hanya membatalkan yang lainnya.

O (N ^ 3)

Anda harus bertemu orang lain dan, selama setiap pertemuan, Anda harus berbicara tentang orang lain di ruangan itu.

O (1)

Tuan rumah ingin mengumumkan sesuatu. Mereka membawa gelas anggur dan berbicara dengan keras. Semua orang mendengarnya. Ternyata tidak masalah berapa banyak peserta yang hadir, operasi ini selalu memakan waktu yang sama.

O (log N)

Tuan rumah telah meletakkan semua orang di meja dalam urutan abjad. Dimanakah Dan? Anda beralasan bahwa dia pasti berada di suatu tempat antara Adam dan Mandy (tentu saja bukan antara Mandy dan Zach!). Mengingat itu, apakah dia antara George dan Mandy? Tidak. Dia pasti antara Adam dan Fred, dan antara Cindy dan Fred. Dan seterusnya ... kita dapat menemukan Dan dengan efisien dengan melihat setengah dari set dan kemudian setengah dari set itu. Pada akhirnya, kita melihat O (log_2 N) individu.

O (N log N)

Anda bisa menemukan tempat duduk di meja menggunakan algoritma di atas. Jika sejumlah besar orang datang ke meja, satu per satu, dan semua melakukan ini, itu akan membutuhkan waktu O (N log N) . Ini ternyata menjadi berapa lama yang dibutuhkan untuk mengurutkan koleksi barang ketika mereka harus dibandingkan.

Kasus Terbaik / Terburuk

Anda tiba di pesta dan perlu menemukan Inigo - berapa lama? Itu tergantung kapan Anda tiba. Jika semua orang berkeliaran di sekitar Anda telah mencapai yang terburuk: itu akan memakan O(N)waktu. Namun, jika semua orang duduk di meja, itu hanya akan memakan O(log N)waktu. Atau mungkin Anda dapat memanfaatkan kekuatan berteriak gelas anggur tuan rumah dan itu hanya akan memakan O(1)waktu.

Dengan asumsi tuan rumah tidak tersedia, kita dapat mengatakan bahwa algoritma pencarian Inigo memiliki batas bawah O(log N)dan batas atas O(N), tergantung pada keadaan pesta ketika Anda tiba.

Ruang & Komunikasi

Gagasan yang sama dapat diterapkan untuk memahami bagaimana algoritma menggunakan ruang atau komunikasi.

Knuth telah menulis makalah yang bagus tentang mantan berjudul "The Complexity of Songs" .

Teorema 2: Ada banyak lagu kompleksitas O (1) yang sewenang-wenang.

BUKTI: (karena Casey dan Sunshine Band). Pertimbangkan lagu Sk ditentukan oleh (15), tetapi dengan

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

untuk semua k.

Saya tahu pertanyaan ini berjalan jauh ke belakang dan ada beberapa jawaban yang sangat baik di sini, namun saya ingin berbagi sedikit untuk orang-orang yang berpikiran matematis yang akan tersandung dalam posting ini. The Guru teorema adalah hal berguna lain untuk tahu kapan belajar kompleksitas. Saya tidak melihatnya disebutkan dalam jawaban lain.

O (n) adalah notasi O besar yang digunakan untuk menulis kompleksitas waktu suatu algoritma. Saat Anda menjumlahkan jumlah eksekusi dalam algoritme Anda akan mendapatkan ekspresi dalam hasil seperti 2N + 2, dalam ungkapan ini N adalah istilah yang mendominasi (istilah yang memiliki efek terbesar pada ekspresi jika nilainya meningkat atau menurun). Sekarang O (N) adalah waktu comlexity sementara N mendominasi istilah. Contoh

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

di sini jumlah total eksekusi untuk loop dalam adalah n + 1 dan jumlah total eksekusi untuk loop luar adalah n (n + 1) / 2, sehingga jumlah total eksekusi untuk seluruh algoritma adalah n + 1 + n (n + 1/2 ) = (n ^ 2 + 3n) / 2. di sini n ^ 2 adalah istilah yang mendominasi sehingga kompleksitas waktu untuk algoritma ini adalah O (n ^ 2)