Saya memiliki loop sederhana seperti ini:
for (int i = 0; i < n; i++) {
// constant time operation
}
Sangat mudah untuk melihat bahwa kompleksitas waktunya adalah O(n), tetapi jika kita menghitungnya, mengapa 2*n + 2 + c*n (jawaban yang diberikan) dan bukan (1+ (n+1) + 2*n + c*n) = (3+c)*n + 2? Saya melihat i++ sebagai 2 operasi: penambahan dan penugasan; jadi, seharusnya 2*n, dan operasi konstan dijalankan n kali, jadi c*n.
2*n
(n perbandingan (i<n) + n kenaikan (i++)) == 2*n
2
(i=0 1 untuk tugas + 1 untuk alokasi i) == 2
c*n
(n operasi waktu konstan) == c*n
Dari apa yang saya tahu, kenaikan/penurunan diperlakukan sebagai operasi tunggal. Ini masuk akal karena dalam perakitan, Anda dapat melakukan penambahan atau pengurangan dengan satu baris kode perakitan. Selain itu, sebagian besar baris kode perakitan diterjemahkan langsung ke instruksi biner tunggal. Jadi, kenaikan/penurunan secara efektif merupakan operasi waktu yang konstan.
Oleh karena itu, kami memiliki n operasi dari penambahan. Kami juga menjalankan badan perulangan sebanyak n kali, dan badan perulangan melakukan operasi waktu yang konstan, jadi kami memiliki operasi c * n tambahan. Saat kita memasuki loop untuk pertama kalinya, ada operasi penugasan tambahan. Ini menghasilkan operasi lain. Terakhir, setelah perulangan berjalan untuk kesekian kalinya, perulangan memeriksa kondisi perulangan sekali lagi. Artinya ada n + 1 perbandingan yang dilakukan perulangan.
Jika dijumlahkan, kita mendapatkan n + c * n + 1 + (n + 1) = 2 * n + c * n + 2, yang merupakan jawaban yang Anda lihat.
