Apakah ini akan diklasifikasikan sebagai algoritma O (1) untuk "Halo, Dunia!" ??

public class Hello1
{
   public static void Main()
   {
      DateTime TwentyYearsLater = new DateTime(2035,01,01);
      while ( DateTime.Now < TwentyYearsLater )
      { 
          System.Console.WriteLine("It's still not time to print the hello ...");
      }
      System.Console.WriteLine("Hello, World!");
   }
}

Saya sedang berpikir untuk menggunakan

DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{ 
   // ... 
}

potongan kode sebagai loop sibuk untuk dimasukkan sebagai lelucon setiap kali seseorang meminta algoritme dengan kompleksitas tertentu. Apakah ini benar?

Notasi Big O dalam konteks ini digunakan untuk menggambarkan hubungan antara ukuran input dari suatu fungsi dan jumlah operasi yang perlu dilakukan untuk menghitung hasil untuk input tersebut.

Operasi Anda tidak memiliki input yang dapat dikaitkan dengan output, jadi menggunakan notasi Big O tidak masuk akal. Waktu yang dibutuhkan operasi tidak tergantung pada input operasi (yang ... tidak ada). Karena ada adalah ada hubungan antara input dan jumlah operasi yang dilakukan, Anda tidak dapat menggunakan Big O untuk menggambarkan bahwa hubungan tidak ada

Notasi Big-O berarti kira-kira 'diberi operasi pada sejumlah pekerjaan, N, berapa banyak waktu kalkulasi, sebanding dengan N, yang dibutuhkan algoritme?'. Misalnya, mengurutkan array dengan ukuran N dapat menggunakan N ^ 2, Nlog (N), dll.

Ini tidak memiliki jumlah data masukan untuk ditindaklanjuti. Jadi tidak O(anything).

Lebih buruk lagi; ini secara teknis bukanlah sebuah algoritma. Algoritme adalah metode untuk menghitung nilai fungsi matematika - fungsi matematika adalah pemetaan dari satu masukan ke keluaran. Karena ini tidak mengambil masukan dan tidak mengembalikan apa-apa, ini bukan fungsi, dalam pengertian matematis. Dari wikipedia:

Algoritme adalah metode efektif yang dapat diekspresikan dalam ruang dan waktu yang terbatas dan dalam bahasa formal yang terdefinisi dengan baik untuk menghitung suatu fungsi. Dimulai dari keadaan awal dan masukan awal (mungkin kosong), instruksi menggambarkan komputasi yang, ketika dijalankan, berlanjut melalui sejumlah keadaan berurutan yang terdefinisi dengan baik, akhirnya menghasilkan "keluaran" dan berakhir pada keadaan akhir akhir.

Secara teknis, ini adalah sistem kendali. Dari wikipedia;

Sistem kontrol adalah perangkat, atau sekumpulan perangkat, yang mengelola, memerintahkan, mengarahkan, atau mengatur perilaku perangkat atau sistem lain.

Bagi orang-orang yang menginginkan jawaban yang lebih mendalam tentang perbedaan antara fungsi matematika dan algoritme, dan kemampuan komputer yang lebih kuat untuk melakukan hal-hal yang mempengaruhi seperti keluaran konsol, menampilkan grafik, atau mengendalikan robot, bacalah makalah ini di Hipotesis Church-Turing yang Kuat

Abstrak

Pandangan klasik komputasi memposisikan komputasi sebagai transformasi input kotak tertutup (bilangan rasional atau string terbatas) menjadi output. Menurut pandangan komputasi interaktif, komputasi adalah proses interaktif yang sedang berlangsung daripada transformasi berbasis fungsi dari input menjadi output. Secara khusus, komunikasi dengan dunia luar terjadi selama penghitungan, bukan sebelum atau sesudahnya. Pendekatan ini secara radikal mengubah pemahaman kita tentang apa itu komputasi dan bagaimana ia dimodelkan.

Penerimaan interaksi sebagai paradigma baru terhalang oleh Strong Church-Turing Thesis (SCT), kepercayaan luas bahwa Turing Machines (TMs) menangkap semua komputasi, sehingga model komputasi yang lebih ekspresif daripada TM tidak mungkin dilakukan. Dalam makalah ini, kami menunjukkan bahwa SCT menafsirkan ulang Tesis Church-Turing (CTT) asli dengan cara yang tidak pernah dimaksudkan Turing; kesamaannya yang umumnya diasumsikan dengan aslinya adalah mitos. Kami mengidentifikasi dan menganalisis alasan historis untuk kepercayaan luas pada SCT. Hanya dengan menerima bahwa itu salah kita dapat mulai mengadopsi interaksi sebagai paradigma komputasi alternatif

Tidak, kode Anda memiliki kerumitan waktu O(2^|<DeltaTime>|),

Untuk pengkodean waktu yang tepat.
Tolong, izinkan saya meminta maaf terlebih dahulu untuk bahasa Inggris saya.

Apa itu dan bagaimana Big O bekerja di CS

Notasi Big O tidak digunakan untuk mengikat input program dengan waktu berjalannya .
Notasi O besar adalah, meninggalkan kekakuan, cara untuk mengekspresikan rasio asimtotik dua kuantitas .

Dalam kasus analisis algoritme, kedua kuantitas ini bukanlah input (yang pertama harus memiliki fungsi "ukur") dan waktu berjalan.
Mereka adalah panjang pengkodean sebuah instance dari masalah ¹ dan metrik yang diminati.

Metrik yang umum digunakan adalah

1. Jumlah langkah yang diperlukan untuk menyelesaikan algoritme dalam model komputasi tertentu.
2. Ruang yang dibutuhkan, jika ada konsep seperti itu, oleh model komputasi.

Implisit diasumsikan TM sebagai model sehingga titik pertama diterjemahkan ke sejumlah aplikasi dari transisi ² fungsi , yaitu "langkah", dan yang kedua diterjemahkan jumlah sel pita yang berbeda ditulis setidaknya sekali .

Apakah juga sering secara implisit diasumsikan bahwa kita dapat menggunakan pengkodean terkait polinomial daripada yang asli, misalnya fungsi yang mencari array dari awal hingga akhir memiliki O(n)kompleksitas terlepas dari kenyataan bahwa pengkodean sebuah instance dari array tersebut harus memiliki panjang n*b+(n-1)dimana badalah jumlah simbol (konstan) dari setiap elemen. Ini karena bdianggap sebagai konstanta dari model komputasi sehingga ekspresi di atas dan nsecara asimtotik sama.

Ini juga menjelaskan mengapa algoritma seperti Trial Division adalah algoritma eksponensial meskipun pada dasarnya merupakan for(i=2; i<=sqr(N); i++)algoritma ³ .

Lihat ini .

Ini juga berarti bahwa notasi O besar dapat menggunakan sebanyak mungkin parameter yang mungkin dibutuhkan seseorang untuk mendeskripsikan masalah, bukankah tidak biasa untuk memiliki parameter k untuk beberapa algoritme.

Jadi ini bukan tentang "masukan" atau "tidak ada masukan".

Pelajari kasus sekarang

Notasi Big O tidak mempertanyakan algoritme Anda, ini hanya mengasumsikan bahwa Anda tahu apa yang Anda lakukan. Ini pada dasarnya adalah alat yang dapat diterapkan di mana saja, bahkan untuk algoritme yang mungkin sengaja dibuat rumit (seperti milik Anda).

Untuk mengatasi masalah Anda, Anda menggunakan tanggal saat ini dan tanggal yang akan datang, jadi keduanya pasti menjadi bagian dari masalah; sederhananya: mereka adalah bagian dari contoh masalah.

Secara khusus contohnya adalah:

<DeltaTime>

Dimana <>cara apapun, non patologis, pengkodean pilihan.

Lihat di bawah untuk klarifikasi yang sangat penting .

Jadi waktu kompleksitas O besar Anda adalah adil O(2^|<DeltaTime>|), karena Anda melakukan sejumlah iterasi yang bergantung pada nilai waktu saat ini. Tidak ada gunanya menempatkan konstanta numerik lain karena notasi asimtotik berguna karena menghilangkan konstanta (jadi misalnya penggunaan O(10^|<DeltaTime>|*any_time_unit)tidak ada gunanya).

Dimana bagian yang sulit

Kami membuat satu asumsi penting di atas: bahwa model komputasi sertifikat ⁵ waktu, dan waktu yang saya maksud adalah waktu fisik (nyata?). Tidak ada konsep seperti itu dalam model komputasi standar, TM tidak tahu waktu, kami menghubungkan waktu dengan jumlah langkah karena beginilah cara kerja realitas kami ⁴ .

Dalam model Anda, bagaimanapun waktu adalah bagian dari perhitungan, Anda dapat menggunakan terminologi orang fungsional dengan mengatakan bahwa Utama tidak murni tetapi konsepnya sama.

Untuk memahami hal ini, perlu dicatat bahwa tidak ada yang menghalangi Framework untuk menggunakan waktu palsu yang berjalan dua kali, lima, sepuluh kali lebih cepat dari waktu fisik. Dengan cara ini kode Anda akan berjalan di "setengah", "seperlima", "sepersepuluh" dari "waktu".

Refleksi ini penting untuk memilih pengkodean <DeltaTime>, ini pada dasarnya adalah cara penulisan yang ringkas <(CurrentTime, TimeInFuture)>. Karena waktu tidak ada di priorat, pengkodean CurrentTime bisa jadi kata Sekarang (atau pilihan lain) sehari sebelumnya dapat dikodekan sebagai Kemarin , di sana dengan melanggar asumsi bahwa panjang pengkodean bertambah sebagai waktu fisik maju (dan salah satu DeltaTime berkurang)

Kita harus memodelkan waktu dengan benar dalam model komputasi kita untuk melakukan sesuatu yang berguna.

Satu-satunya pilihan aman yang dapat kita lakukan adalah menyandikan stempel waktu dengan panjang yang bertambah (tetapi tetap tidak menggunakan unary) saat waktu fisik bergerak maju. Ini adalah satu-satunya properti sebenarnya dari waktu yang kita butuhkan dan properti yang perlu ditangkap oleh encoding. Apakah hanya dengan jenis pengkodean inilah algoritme Anda mungkin diberi kompleksitas waktu.

Kebingungan Anda, jika ada, muncul dari fakta bahwa kata waktu dalam frasa 'Apa kerumitan waktunya ?' dan 'Berapa lama waktu yang dibutuhkan?' Berarti untuk hal yang sangat berbeda

Sayangnya terminologi menggunakan kata yang sama, tetapi Anda dapat mencoba menggunakan "kerumitan langkah" di kepala Anda dan menanyakan kembali pertanyaan Anda pada diri sendiri, saya harap itu akan membantu Anda memahami jawabannya sebenarnya adalah ^ _ ^

¹ Ini juga menjelaskan perlunya pendekatan asimtotik karena setiap instance memiliki panjang yang berbeda, namun tidak sewenang-wenang.
² Saya harap saya menggunakan istilah bahasa Inggris yang benar di sini.
³ Juga inilah mengapa kita sering menemukan log(log(n))istilah dalam matematika.
⁴ Id est, langkah harus menempati interval waktu yang terbatas, tetapi tidak null, atau tidak terhubung.
⁵ Ini berarti bahwa mode komputasi sebagai pengetahuan tentang waktu fisik di dalamnya, yang dapat mengekspresikannya dengan istilah-istilahnya. Sebuah analogi adalah bagaimana obat generik bekerja dalam kerangka .NET.

Meskipun ada banyak jawaban bagus di sini, izinkan saya mengulanginya sedikit.

Notasi Big-O ada untuk mendeskripsikan fungsi . Ketika diterapkan pada analisis algoritme, ini mengharuskan kami untuk terlebih dahulu mendefinisikan beberapa karakteristik algoritme ini dalam istilah suatu fungsi . Pilihan umum adalah mempertimbangkan jumlah langkah sebagai fungsi ukuran input . Seperti dicatat dalam jawaban lain, muncul dengan fungsi seperti itu dalam kasus Anda tampak aneh, karena tidak ada "masukan" yang didefinisikan dengan jelas. Kami masih dapat mencoba melakukannya, meskipun:

• Kami dapat menganggap algoritme Anda sebagai fungsi konstan yang mengambil masukan apa pun dengan ukuran berapa pun, mengabaikannya, menunggu waktu tertentu, dan menyelesaikannya. Dalam hal ini runtime-nya adalah f (n) = const , dan itu adalah algoritma O (1) -time. Ini yang Anda harapkan untuk didengar, bukan? Ya, secara teknis, ini adalah algoritme O (1) .
• Kita dapat menganggapnya TwentyYearsLatersebagai parameter yang disukai "ukuran masukan". Dalam hal ini runtime adalah f (n) = (nx) di mana x adalah "waktu sekarang" pada saat pemanggilan. Jika dilihat seperti ini, itu adalah algoritma O (n) -time. Harapkan argumen balasan ini setiap kali Anda menunjukkan algoritme teknis O (1) Anda kepada orang lain.
• Oh, tapi tunggu, jika k =TwentyYearsLater adalah inputnya, maka ukurannya n adalah jumlah bit yang dibutuhkan untuk mewakilinya, yaitu n = log (k) . Oleh karena itu, ketergantungan antara ukuran masukan n dan runtime adalah f (n) = 2 ^ n - x . Sepertinya algoritme Anda menjadi sangat lambat secara eksponensial! Ugh.
• Masukan lain untuk program ini sebenarnya adalah aliran jawaban yang diberikan oleh OS ke urutan DateTime.Nowpemanggilan dalam loop. Kita sebenarnya dapat membayangkan bahwa seluruh urutan ini disediakan sebagai masukan pada saat kita menjalankan program. Runtime kemudian dapat dianggap bergantung pada properti urutan ini - yaitu panjangnya hingga TwentyYearsLaterelemen pertama . Dalam hal ini runtime sekali lagi adalah f (n) = n dan algoritmanya adalah O (n) .

Tapi sekali lagi, dalam pertanyaan Anda, Anda bahkan tidak mengatakan bahwa Anda tertarik dengan runtime. Bagaimana jika yang Anda maksud adalah penggunaan memori? Bergantung pada bagaimana Anda memodelkan situasi, Anda dapat mengatakan algoritmanya adalah O (1) -memori atau, mungkin, O (n) -memori (jika implementasi dari Requirement DateTime.Nowuntuk melacak seluruh urutan pemanggilan kadang-kadang).

Dan jika tujuan Anda adalah menghasilkan sesuatu yang tidak masuk akal, mengapa Anda tidak membahas semuanya dan mengatakan bahwa Anda tertarik pada bagaimana ukuran kode algoritme dalam piksel di layar bergantung pada tingkat zoom yang dipilih. Ini mungkin seperti f (zoom) = 1 / zoom dan Anda dapat dengan bangga menyatakan algoritme Anda menjadi O (1 / n) -piksel!

Saya harus sedikit tidak setuju dengan Servy. Ada masukan untuk program ini, meskipun tidak jelas, dan itulah waktu sistem. Ini mungkin teknis yang tidak Anda inginkan, tetapi TwentyYearsFromNowvariabel Anda tidak dua puluh tahun dari waktu sistem sekarang , itu secara statis ditetapkan ke 1 Januari 2035.

Jadi jika Anda mengambil kode ini dan menjalankannya pada mesin yang memiliki waktu sistem 1 Januari 1970, akan memakan waktu 65 tahun untuk menyelesaikannya, terlepas dari seberapa cepat komputernya (mungkin ada beberapa variasi jika jamnya rusak) ). Jika Anda mengambil kode ini dan menjalankannya pada mesin yang memiliki waktu sistem 2 Januari 2035, itu akan selesai hampir seketika.

Saya akan mengatakan masukan Anda n,, adalah January 1st, 2035 - DateTime.Now, dan itu O (n).

Lalu ada juga masalah jumlah operasi. Beberapa orang telah memperhatikan bahwa komputer yang lebih cepat akan melakukan loop lebih cepat, menyebabkan lebih banyak operasi, tetapi itu tidak relevan. Saat bekerja dengan notasi O besar, kami tidak mempertimbangkan kecepatan prosesor atau jumlah operasi yang tepat. Jika Anda mengambil algoritme ini dan menjalankannya di komputer, lalu menjalankannya lagi tetapi 10x lebih lama di komputer yang sama, Anda akan mengharapkan jumlah operasi bertambah dengan faktor yang sama yaitu 10x.

Adapun ini:

Saya berpikir untuk menggunakan potongan kode [kode yang dihapus] sebagai loop sibuk untuk dijadikan lelucon setiap kali seseorang meminta algoritme dengan kompleksitas tertentu. Apakah ini benar?

Tidak terlalu. Jawaban lain telah mencakup ini, jadi saya hanya ingin menyebutkannya. Biasanya Anda tidak dapat menghubungkan tahun eksekusi dengan notasi O besar. Misalnya. Tidak ada cara untuk mengatakan 20 tahun eksekusi = O (n ^ 87) atau apa pun dalam hal ini. Bahkan dalam algoritme yang Anda berikan, saya dapat mengubah TwentyYearsFromNowke tahun 20110, 75699436, atau 123456789 dan O besar tetap O (n).

Analisis Big-O berkaitan dengan jumlah pemrosesan yang terlibat karena jumlah data yang diproses meningkat tanpa batas.

Di sini, Anda benar-benar hanya berurusan dengan satu objek dengan ukuran tetap. Dengan demikian, menerapkan analisis Big-O sangat bergantung (terutama?) Pada cara Anda mendefinisikan istilah Anda.

Misalnya, yang Anda maksud adalah hasil cetak secara umum, dan memaksakan menunggu begitu lama sehingga sejumlah data yang wajar akan / akan dicetak dalam periode waktu yang persis sama. Anda juga harus menambahkan sedikit lebih banyak dengan cara definisi yang agak tidak biasa (jika tidak salah) untuk menjadi sangat jauh - terutama, analisis big-O biasanya didefinisikan dalam istilah jumlah operasi fundamental yang diperlukan untuk melaksanakan tugas tertentu (tetapi perhatikan bahwa kompleksitas juga dapat dipertimbangkan dalam hal hal-hal seperti penggunaan memori, bukan hanya penggunaan / operasi CPU yang dilakukan).

Jumlah operasi dasar biasanya diterjemahkan cukup dekat dengan waktu yang dibutuhkan, bagaimanapun, jadi tidak terlalu besar memperlakukan keduanya sebagai sinonim. Sayangnya, bagaimanapun, kami masih terjebak dengan bagian lain itu: jumlah data yang sedang diproses meningkat tanpa batas. Karena itu, tidak ada penundaan tetap yang dapat Anda terapkan akan benar-benar berhasil. Untuk menyamakan O (1) dengan O (N), Anda harus memberlakukan penundaan tak terbatas sehingga jumlah data tetap membutuhkan waktu lama untuk dicetak, sama seperti jumlah data yang tak terbatas.

besar-O relatif terhadap apa?

Anda tampaknya intuitif itu twentyYearsLateradalah "masukan". Jika memang Anda menulis fungsi Anda sebagai

void helloWorld(int years) {
   // ...
}

Ini akan menjadi O (N) di mana N = tahun (atau katakan saja O(years)).

Saya akan mengatakan algoritme Anda adalah O (N) relatif terhadap angka apa pun yang kebetulan Anda tulis di baris kode yang dimulai dengan twentyYearsLater =. Tetapi orang biasanya tidak menganggap angka dalam kode sumber sebenarnya sebagai masukan. Mereka mungkin menganggap masukan baris perintah sebagai masukan, atau masukan tanda tangan fungsi sebagai masukan, tetapi, kemungkinan besar bukan kode sumber itu sendiri. Itulah yang Anda perdebatkan dengan teman Anda - apakah ini "masukan"? Anda mengatur kode Anda sedemikian rupa sehingga secara intuitif tampak seperti input, dan Anda pasti dapat menanyakan waktu berjalan O besar sehubungan dengan nomor N pada baris 6 program Anda, tetapi jika Anda menggunakan pilihan non-default seperti itu sebagai masukan Anda benar-benar perlu menjelaskannya secara eksplisit.

Tetapi jika Anda menganggap input menjadi sesuatu yang lebih biasa, seperti baris perintah atau input ke fungsi, tidak ada output sama sekali dan fungsinya adalah O (1). Dibutuhkan dua puluh tahun, tetapi karena O besar tidak berubah menjadi kelipatan konstan, O (1) = O (dua puluh tahun).

Pertanyaan serupa - apa runtime dari:

void sortArrayOfSizeTenMillion(int[] array)

Dengan asumsi itu melakukan apa yang dikatakan dan inputnya valid, dan algoritme memanfaatkan quicksort atau bubble sort atau apa pun yang masuk akal, itu adalah O (1).

"Algoritme" ini dengan tepat dijelaskan sebagai O (1) atau waktu konstan. Dikatakan bahwa tidak ada masukan untuk program ini, oleh karena itu tidak ada N untuk dianalisis dalam kaitannya dengan Big Oh. Saya tidak setuju bahwa tidak ada masukan. Saat ini dikompilasi menjadi file yang dapat dieksekusi dan dipanggil, pengguna dapat menentukan input apa pun dengan panjang arbitrer. Panjang masukan itu adalah N.

Program hanya mengabaikan input (berapa pun lamanya), jadi waktu yang dibutuhkan (atau jumlah instruksi mesin yang dieksekusi) sama terlepas dari panjang input (diberikan lingkungan tetap = waktu mulai + perangkat keras), maka O (1 ).

Satu hal yang mengejutkan saya belum disebutkan: notasi O besar adalah batas atas!

Masalah yang diperhatikan semua orang adalah bahwa tidak ada N yang mendeskripsikan input ke algoritme, jadi tidak ada yang perlu dilakukan analisis big-O. Namun, ini mudah diatasi dengan beberapa tipuan dasar, seperti menerima int ndan mencetak waktu "Hello World" n. Itu akan mengatasi keluhan itu dan kembali ke pertanyaan sebenarnya tentang bagaimana ituDateTime monster itu bekerja.

Sebenarnya tidak ada jaminan bahwa loop sementara akan berhenti. Kami suka berpikir itu harus pada suatu waktu, tetapi pertimbangkan bahwa DateTime.nowmengembalikan tanggal dan waktu sistem . Sebenarnya tidak ada jaminan bahwa ini meningkat secara monoton. Ada kemungkinan bahwa ada beberapa monyet yang terlatih secara patologis yang terus-menerus mengubah tanggal dan waktu sistem kembali ke 21 Oktober 2015 12:00:00 UTC sampai seseorang memberi monyet beberapa sepatu pas otomatis dan papan hover. Putaran ini sebenarnya dapat berjalan untuk waktu yang tidak terbatas!

Saat Anda benar-benar menggali definisi matematika dari notasi O besar, mereka adalah batas atas. Mereka mendemonstrasikan skenario terburuk, betapapun kecil kemungkinannya. Skenario kasus terburuk * di sini adalah runtime tak terbatas, jadi kami dipaksa untuk menyatakan bahwa tidak ada notasi O besar untuk menggambarkan kompleksitas runtime dari algoritme ini. Itu tidak ada, sama seperti 1/0 tidak ada.

* Sunting: dari diskusi saya dengan KT, tidak selalu valid untuk menganggap skenario yang kita modelkan dengan notasi O besar adalah kasus terburuk. Dalam kebanyakan kasus, jika seseorang gagal menentukan kasus mana yang kami gunakan, mereka bermaksud untuk menjelajahi kasus terburuk. Namun, Anda dapat melakukan analisis kompleksitas big-O pada runtime kasus terbaik.

Kompleksitas digunakan untuk mengukur "tenaga kuda" komputasi dalam hal waktu / ruang. Notasi Big O digunakan untuk membandingkan masalah mana yang "dapat dihitung" atau "tidak dapat dihitung" dan juga untuk membandingkan solusi -algoritma- mana yang lebih baik dari yang lain. Dengan demikian, Anda dapat membagi algoritme apa pun menjadi dua kategori: algoritme yang dapat diselesaikan dalam waktu polinomial dan yang tidak dapat diselesaikan.

Masalah seperti Saringan Erathostene adalah O (n ^ exp) dan dengan demikian dapat dipecahkan untuk nilai n yang kecil. Mereka dapat dihitung, hanya saja tidak dalam waktu polinomial (NP) dan dengan demikian ketika ditanya apakah suatu bilangan prima atau tidak, jawabannya tergantung pada besarnya bilangan tersebut. Selain itu, kompleksitas tidak bergantung pada perangkat keras, jadi memiliki komputer yang lebih cepat tidak mengubah apa pun ...

Hello World bukanlah sebuah algoritma dan oleh karena itu tidak masuk akal untuk mencoba menentukan kompleksitasnya -yang tidak ada. Algoritme sederhana dapat berupa: diberi nomor acak, tentukan apakah itu genap atau ganjil. Sekarang, apakah penting bahwa bilangan yang diberikan memiliki 500 digit? Tidak, karena Anda hanya perlu memeriksa apakah digit terakhir genap atau ganjil. Algoritme yang lebih kompleks adalah menentukan apakah suatu bilangan dibagi secara merata dengan 3. Meskipun beberapa bilangan "mudah" dihitung, yang lain "sulit" dan ini karena besarnya: bandingkan waktu yang diperlukan untuk menentukan pengingat antara nomor dengan satu digit dan lainnya dengan 500 digit.

Kasus yang lebih kompleks adalah memecahkan kode teks. Anda memiliki rangkaian simbol acak yang juga Anda ketahui sedang menyampaikan pesan bagi mereka yang memiliki kunci dekripsi. Misalkan pengirim menggunakan kunci di sebelah kiri dan Hello World Anda akan membaca: Gwkki Qieks. Solusi "palu besar, tanpa otak" akan menghasilkan semua kombinasi untuk huruf-huruf itu: dari Aaaa ke Zzzz dan kemudian mencari kamus kata untuk mengidentifikasi kata mana yang valid dan berbagi dua huruf umum di sandi (i, k) di posisi yang sama. Fungsi transformasi inilah yang diukur Big O!

Kebanyakan orang tampaknya melewatkan dua hal yang sangat penting.

1. Program ini tidak memiliki masukan. Ini adalah tanggal / waktu hard-code yang digunakan untuk membandingkan waktu sistem. Input berada di bawah kendali orang yang menjalankan algoritme, dan waktu sistem tidak. Satu-satunya hal yang dapat dikontrol oleh orang yang menjalankan program ini adalah tanggal / waktu mereka telah memasukkan hardcode ke dalam perbandingan.

2. Program ini bervariasi berdasarkan masukan nilai , tetapi bukan ukuran input set , yang adalah apa notasi O besar berkaitan dengan.

Oleh karena itu, ini tidak pasti, dan notasi 'besar-O' terbaik untuk program ini mungkin adalah O (null), atau mungkin O (NaN).

Semua orang dengan benar menunjukkan bahwa Anda tidak mendefinisikan N , tetapi jawabannya tidak di bawah interpretasi yang paling masuk akal. Jika N adalah panjang string yang kita cetak dan “halo, dunia!” hanyalah sebuah contoh, karena kita dapat menyimpulkan dari deskripsi ini sebagai algoritme "untuk" hello, world!, maka algoritme tersebut adalah O ( N ), karena Anda mungkin memiliki string keluaran yang membutuhkan waktu tiga puluh, empat puluh, atau lima puluh tahun untuk mencetak, dan Anda hanya menambahkan waktu yang konstan untuk itu. O ( kN + c ) ∈ O ( N ).

Tambahan:

Yang mengejutkan saya, seseorang memperdebatkan hal ini. Ingat definisi dari O besar dan besar. Asumsikan kita memiliki algoritme yang menunggu sejumlah waktu konstan c dan kemudian mencetak pesan dengan panjang N dalam waktu linier. (Ini adalah generalisasi dari contoh kode asli.) Anggap saja kita menunggu dua puluh tahun untuk mulai mencetak, dan pencetakan satu triliun karakter membutuhkan dua puluh tahun lagi. Misalkan c = 20 dan k = 10¹², tetapi bilangan real positif apa pun bisa digunakan. Itu tingkat d = c / k (dalam hal ini 2 × 10⁻¹¹) tahun per karakter, jadi waktu eksekusi kita f ( N ) adalah asimtotikdN + ctahun. Kapanpun N > k , dN = c / k N > c . Oleh karena itu, dN < dN + c = f ( N ) <2 dN untuk semua N > k , dan f ( N ) ∈ Θ ( N ). QED

Saya pikir orang-orang terlempar karena kodenya tidak terlihat seperti algoritma tradisional. Berikut adalah terjemahan kode yang lebih baik, tetapi tetap sesuai dengan semangat pertanyaan OP.

void TrolloWorld(long currentUnixTime, long loopsPerMs){
    long laterUnixTime = 2051222400000;  //unix time of 01/01/2035, 00:00:00
    long numLoops = (laterUnixTime-currentUnixTime)*loopsPerMs;

    for (long i=0; i<numLoops; i++){
        print ("It's still not time to print the hello …");
    }
    print("Hello, World!");
}

Inputnya eksplisit sedangkan sebelumnya secara implisit diberikan pada saat kode dimulai pada dan dengan kecepatan perangkat keras yang menjalankan kode. Kode bersifat deterministik dan memiliki keluaran yang terdefinisi dengan baik untuk masukan yang diberikan.

Karena keterbatasan yang diberlakukan pada input yang dapat kita berikan, ada batasan atas jumlah operasi yang akan dijalankan, jadi algoritma ini sebenarnya adalah O (1).

Pada saat ini, ya

Algoritma ini memiliki input implisit, yaitu saat program dimulai. Waktu eksekusi akan bervariasi secara linier ¹ tergantung kapan dimulai. Selama tahun 2035 dan setelahnya, loop sementara segera keluar dan program berhenti setelah operasi konstan ² . Jadi bisa dikatakan runtime-nya O(max(2035 - start year, 1))³ . Tetapi karena tahun awal kita memiliki nilai minimum, algoritme tidak akan membutuhkan waktu lebih dari 20 tahun untuk dieksekusi (yaitu nilai konstan).

Anda dapat membuat algoritme lebih sesuai dengan maksud Anda dengan mendefinisikan DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0);⁴

¹ Ini berlaku untuk pengertian yang lebih teknis tentang waktu eksekusi yang diukur sebagai jumlah operasi karena ada jumlah operasi maksimum per unit waktu.
² Dengan asumsi pengambilan DateTime.Nowadalah operasi konstan, yang wajar.
³ Saya agak menyalahgunakan notasi O besar di sini karena ini adalah fungsi penurunan sehubungan dengan start year, tetapi kita dapat dengan mudah memperbaiki ini dengan mengekspresikannya dalam bentuk years prior to 2035.
⁴ Maka algoritme tidak lagi bergantung pada masukan implisit dari waktu mulai, tetapi itu bukan konsekuensi.

Saya berpendapat bahwa ini adalah O (n). menggunakan http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html sebagai referensi.

Apa itu Big O?

Notasi Big O berusaha untuk menggambarkan kompleksitas relatif dari suatu algoritma dengan mengurangi tingkat pertumbuhan ke faktor-faktor kunci ketika faktor kunci cenderung ke arah tak terhingga.

dan

Contoh terbaik Big-O yang bisa saya pikirkan adalah melakukan aritmatika. Operasi aritmatika dasar yang kami pelajari di sekolah adalah:

tambahan; pengurangan; perkalian; dan divisi. Masing-masing adalah operasi atau masalah. Metode untuk menyelesaikannya disebut algoritma.

Sebagai contoh Anda,

diberi masukan n = 20 (dengan satuan tahun).

algoritma adalah fungsi matematika f (). di mana f () kebetulan menunggu selama n tahun, dengan string 'debug' di antaranya. Faktor skala adalah 1. f () dapat dikurangi / atau ditingkatkan dengan mengubah faktor skala ini.

untuk kasus ini, outputnya juga 20 (mengubah input mengubah output secara linier).

pada dasarnya fungsinya adalah

f(n) = n*1 = n
    if  n = 20, then 
f(20) = 20