26

Saya telah mendengar beberapa kali bahwa untuk nilai n yang cukup kecil, O (n) dapat dipikirkan / diperlakukan seolah-olah itu O (1).

Contoh :

Motivasi untuk melakukannya didasarkan pada gagasan yang salah bahwa O (1) selalu lebih baik daripada O (lg n), selalu lebih baik daripada O (n). Urutan asimptotik dari operasi hanya relevan jika dalam kondisi realistis ukuran masalah sebenarnya menjadi besar. Jika n tetap kecil maka setiap masalah adalah O (1)!

Apa yang cukup kecil? 10? 100? 1.000? Pada titik apa Anda berkata "kita tidak bisa memperlakukan ini seperti operasi gratis lagi"? Apakah ada aturan praktis?

Sepertinya ini bisa spesifik untuk domain atau kasus, tetapi apakah ada aturan umum tentang cara berpikir tentang ini?

asymptotics rianjs
sumber

4

Aturan praktis tergantung pada masalah yang ingin Anda selesaikan. Cepat pada sistem embedded dengan ? Terbitkan dalam teori kompleksitas?

n \leq 100

$n \leq 100$

Raphael

3

Memikirkannya lebih lanjut, pada dasarnya rasanya mustahil untuk datang dengan satu aturan praktis, karena persyaratan kinerja ditentukan oleh domain Anda dan persyaratan bisnisnya. Dalam lingkungan yang terbatas sumber daya, n bisa jadi cukup besar. Dalam lingkungan yang sangat terbatas, mungkin cukup kecil. Itu tampak jelas sekarang di belakang.

rianjs

12

@rianjs Anda tampaknya akan mengira O(1)untuk bebas . Alasan di balik beberapa kalimat pertama adalah bahwa O(1)adalah konstan , yang kadang-kadang bisa gila-gilaan lambat. Suatu perhitungan yang membutuhkan waktu seribu miliar tahun terlepas dari input adalah suatu O(1)perhitungan.

Mooing Duck

1

Pertanyaan terkait tentang mengapa kami menggunakan asimptotik di tempat pertama.

Raphael

3

@rianjs: waspadai lelucon di sepanjang garis "pentagon kira-kira lingkaran, untuk nilai 5 yang cukup besar". Kalimat yang Anda tanyakan itu benar, tetapi karena itu membuat Anda bingung, mungkin ada baiknya Anda bertanya kepada Eric Lippert, sampai sejauh mana pilihan ungkapan yang tepat ini untuk efek humor. Dia bisa mengatakan, "jika ada batas atas maka setiap masalah adalah " dan secara matematis masih benar. "Kecil" bukan bagian dari matematika.

n

$n$

O (1)

$O(1)$

Steve Jessop

21

Semua urutan besarnya melibatkan konstanta , beberapa di antaranya sebenarnya. Ketika jumlah item cukup besar konstanta tidak relevan. Pertanyaannya adalah apakah jumlah barang cukup kecil sehingga konstan untuk mendominasi. $C$

Inilah cara visual untuk memikirkannya.

masukkan deskripsi gambar di sini

Semua memiliki konstanta startup yang menentukan titik awal mereka pada sumbu Y. Masing-masing juga memiliki konstanta kritis mendominasi seberapa cepat mereka akan meningkat. $C$

Untuk , menentukan waktu. $O(1)$ $C$
$O(n)$ benar-benar , di mana menentukan sudutnya. $C \times n$ $C$
$O(n^2)$ benar-benar , di mana menentukan ketajaman kurva. $(C \times n)^2$ $C$

Untuk menentukan algoritma mana yang harus Anda gunakan, Anda perlu memperkirakan tempat di mana runtimes berpotongan. Misalnya, solusi dengan waktu startup tinggi atau tinggi akan kalah dari solusi dengan waktu startup rendah dan rendah pada jumlah item yang cukup besar. $O(1)$ $C$ $O(n)$ $C$

Inilah contoh dunia nyata. Anda harus memindahkan banyak batu bata ke halaman. Anda dapat memindahkannya sedikit demi sedikit dengan tangan Anda, atau mengambil backhoe yang besar dan lambat untuk mengangkat dan mengarahkannya dalam satu perjalanan. Apa jawaban Anda jika ada tiga batu bata? Apa jawaban Anda jika ada tiga ribu?

Inilah contoh CS. Katakanlah Anda memerlukan daftar yang selalu diurutkan. Anda bisa menggunakan pohon yang akan menjaga dirinya agar . Atau Anda bisa menggunakan daftar yang tidak disortir dan mengurutkan ulang setelah setiap penyisipan atau penghapusan di . Karena operasi pohon rumit (mereka memiliki konstanta tinggi), dan pengurutan sangat sederhana (konstanta rendah), daftar kemungkinan akan menang hingga ratusan atau ribuan item. $O(\log{n})$ $O(n \log{n})$

Anda dapat melihat hal semacam ini, tetapi pada akhirnya pembandingan adalah yang akan melakukannya. Anda juga harus melihat berapa banyak barang yang biasanya Anda miliki, dan mengurangi risiko diserahkan lebih banyak. Anda juga akan ingin mendokumentasikan asumsi Anda seperti "kinerja akan menurun dengan cepat di atas item " atau "kami menganggap ukuran set maksimum ". $X$ $X$

Karena persyaratan ini dapat berubah, penting untuk menempatkan keputusan semacam ini di belakang sebuah antarmuka. Dalam contoh pohon / daftar di atas, jangan memaparkan pohon atau daftar. Dengan begitu, jika asumsi Anda ternyata salah, atau Anda menemukan algoritma yang lebih baik, Anda bisa berubah pikiran. Anda bahkan dapat melakukan hibrida dan secara dinamis beralih algoritma saat jumlah item bertambah.

Schwern
sumber

Tidak ada artinya mengatakan . Apa yang Anda benar-benar berarti adalah bahwa jika waktu berjalan adalah kemudian (dalam banyak kasus) . Jika maka dalam banyak kasus , atau lebih formal . Dan seterusnya. Perhatikan, bagaimanapun, bahwa dalam kasus lain konstanta bervariasi dengan , dalam batas-batas tertentu.

O (1) = O (C)

$O(1) = O(C)$

T = O (1)

$T = O(1)$

T \approx C

$T \approx C$

T = O (n)

$T = O(n)$

T \approx C n

$T \approx Cn$

T = C n + o (n)

$T = Cn + o(n)$

C

$C$

n

$n$

Yuval Filmus

@YuvalFilmus Inilah sebabnya saya suka grafik.

Schwern

Ini adalah jawaban terbaik sejauh ini, intinya adalah seberapa cepat fungsi tumbuh.

Ricardo

1

Grafik yang bagus, tetapi sumbu benar-benar harus diberi label "waktu", bukan "kecepatan".

y

$y$

Ilmari Karonen

1

Apakah garis benar-benar parabola? Itu terlihat sangat datar untuk kecil dan sangat curam untuk besar .

O (n^{2})

$O(n^2)$

n

$n$

n

$n$

David Richerby

44

Ini sebagian besar dukungan piggy pada jawaban yang sudah diposting, tetapi dapat menawarkan perspektif yang berbeda.

Ini mengungkapkan bahwa pertanyaan ini membahas "nilai n cukup kecil ". Inti dari Big-O adalah untuk menggambarkan bagaimana pemrosesan tumbuh sebagai fungsi dari apa yang sedang diproses. Jika data yang sedang diproses tetap kecil, tidak relevan untuk membahas Big-O, karena Anda tidak tertarik dengan pertumbuhan (yang tidak terjadi).

Dengan kata lain, jika Anda menempuh jarak yang sangat dekat, mungkin sama cepatnya untuk berjalan, menggunakan sepeda, atau berkendara. Bahkan mungkin lebih cepat untuk berjalan jika perlu waktu untuk menemukan kunci mobil Anda, atau jika mobil Anda membutuhkan bensin, dll.

Untuk n kecil , gunakan apa pun yang nyaman.

Jika Anda melakukan perjalanan lintas negara, maka Anda perlu mencari cara untuk mengoptimalkan mengemudi, jarak tempuh bahan bakar, dll.

Eric Hughes
sumber

5

"Untuk n kecil, gunakan apa pun yang nyaman." - jika Anda sering melakukan operasi , pilih yang tercepat (untuk Anda ). Lihat juga di sini .

n

$n$

Raphael

4

Metafora yang hebat!

Evorlor

1

Dari sudut pandang matematika murni, kompleksitas asimptotik tidak memberi tahu Anda kapan pun n < infinity.

Gordon Gustafson

15

Kutipannya agak kabur dan tidak tepat. Setidaknya ada tiga cara terkait yang bisa ditafsirkan.

$k$ , tidak valid) dan kemudian mencari jawabannya di tabel (yang membutuhkan waktu konstan: ada jumlah entri yang tetap dalam tabel). Namun, perlu diketahui bahwa ukuran sebenarnya dari tabel mungkin sangat besar. Saya mengatakan hanya ada sejumlah grafik pada seratus simpul dan itu benar. Hanya saja, jumlah hingga lebih besar dari jumlah atom di alam semesta yang dapat diamati.

$\Theta(n^2)$ $cn^2$ $C$ $n_0$ $n\geq n_0$ $cn^2$ $n_0=100,000,000$ $n$ $n^2 < 1000n$ $O(n^{2.3729})$ $O(n^{2.8074})$

$n$ $n^2$ $n^3$ $\Theta(n^2)$ Algoritme masih hanya akan membutuhkan beberapa puluh juta instruksi untuk mengurutkan data Anda, yang tidak banyak waktu pada CPU yang dapat melakukan miliaran instruksi per detik. OK, ada akses memori juga, tetapi bahkan algoritma lambat akan memakan waktu kurang dari satu detik sehingga mungkin lebih baik untuk menggunakan algoritma yang sederhana dan lambat dan melakukannya dengan benar daripada menggunakan algoritma yang rumit dan cepat dan menemukan bahwa itu cepat kilat tapi buggy dan tidak benar-benar mengurutkan data dengan benar.

David Richerby
sumber

4

O (n)

$O(n)$

O (1)

$O(1)$

n

$n$

10 n + 50

$10n + 50$

100000

$100000$

n

$n$

O (n)

$O(n)$

@RANG. Bukankah itu termasuk dalam kasus kedua saya? (Terutama jika saya mengeditnya untuk mengatakan sesuatu yang lebih seperti "Algoritma linier dengan konstanta yang baik mungkin mengalahkan algoritma konstan / logaritmik dengan konstanta buruk"?)

David Richerby

1

Akan baik untuk secara eksplisit menyebutkan pentingnya konstanta ketika n kecil. Itu adalah sesuatu yang mungkin tidak akan terjadi pada seseorang yang belum pernah mendengarnya sebelumnya.

Rob Watts

9

$f (n) = O (n^2)$ $n_0$ $f (n) < c n^2$ $n > n_0$

$c n^2$ $n^2 + 10^{18}$

Di sisi lain, jika Anda hanya menemukan nilai n = 1, 2 dan 3, maka dalam praktiknya tidak ada bedanya apa yang dilakukan f (n) untuk n ≥ 4, jadi sebaiknya Anda juga mempertimbangkan bahwa f ( n) = O (1), dengan c = maks (f (1), f (2), f (3)). Dan itu artinya cukup kecil: Jika klaim bahwa f (n) = O (1) tidak menyesatkan Anda jika satu-satunya nilai f (n) yang Anda temui adalah "cukup kecil".

gnasher729
sumber

5

Jika tidak tumbuh, itu O (1)

Pernyataan penulis agak aksiomatis.

Susunan pertumbuhan menggambarkan apa yang terjadi pada jumlah pekerjaan yang harus Anda lakukan sebagai Npeningkatan. Jika Anda tahu itu Ntidak meningkat, masalah Anda efektif O(1).

Ingat itu O(1)tidak berarti "cepat". Algoritma yang selalu membutuhkan 1 triliun langkah untuk diselesaikan adalah O(1). Algoritma yang mengambil dari 1-200 langkah, tetapi tidak pernah lebih, adalah O(1). [1]

Jika algoritma Anda mengambil N ^ 3langkah tepat , dan Anda tahu itu Ntidak boleh lebih dari 5, itu tidak akan pernah bisa lebih dari 125 langkah, jadi itu efektif O(1).

Tetapi sekali lagi, O(1)tidak harus berarti "cukup cepat". Itu pertanyaan terpisah yang tergantung pada konteks Anda. Jika butuh satu minggu untuk menyelesaikan sesuatu, Anda mungkin tidak peduli apakah itu secara teknis O(1).

[1] Misalnya, pencarian dalam hash adalah O(1), meskipun tabrakan hash berarti bahwa Anda mungkin harus melihat beberapa item dalam satu ember, asalkan ada batasan keras tentang berapa banyak item yang bisa berada di ember itu.

Nathan Long
sumber

1

Semua itu kedengarannya valid, kecuali untuk ini: "Jika algoritme Anda mengambil tepat N ^ 3 langkah, dan Anda tahu bahwa N tidak boleh lebih dari 5, itu tidak pernah bisa mengambil lebih dari 125 langkah, jadi itu O (1)." . Sekali lagi, jika suatu algoritma mengambil integer, dan dukungan max integer saya adalah 32767, apakah itu O (1)? Tentu saja tidak. Big-O tidak berubah berdasarkan batas parameter. Ini O (n) bahkan jika Anda tahu bahwa 0 <n <3 karena n = 2 memakan waktu dua kali lebih lama dari n = 1.

JSobell

3

@ JSobell Tapi itu O (1). Jika ada batasan yang membatasi n Anda untuk f (n), itu berarti ia tidak dapat tumbuh tanpa batas. Jika n Anda dibatasi oleh 2 ^ 15, fungsi n ^ 2 Anda yang hebat sebenarnya g(n) = min(f(2^15), f(n))- yang ada di O (1). Yang mengatakan dalam prakteknya konstanta sangat penting dan jelas n dapat menjadi cukup besar sehingga analisis asimptotik berguna.

Voo

2

@ JSobell Ini mirip dengan pertanyaan apakah komputer benar-benar "Turing Lengkap", mengingat bahwa mereka secara teknis tidak dapat memiliki ruang penyimpanan tanpa batas. Secara teknis, matematis, komputer bukanlah Mesin Turing "sejati". Dalam praktiknya, tidak ada yang namanya "pita tak terbatas", tetapi hard drive cukup dekat.

Kyle Strand

Saya menulis sebuah sistem Risiko Keuangan beberapa tahun yang lalu yang melibatkan manipulasi matriks n5, sehingga memiliki batas praktis n = 20 sebelum sumber daya menjadi masalah.

JSobell

Maaf, terlalu cepat tekan Enter. Saya menulis sistem Risiko Keuangan beberapa tahun yang lalu yang melibatkan manipulasi matriks n ^ 5, sehingga memiliki batas praktis n = 20 sebelum sumber daya menjadi masalah. Menurut logika cacat ini, fungsi yang dibuat adalah O (1) karena saya memiliki batas 20. Ketika klien mengatakan "Hmm, mungkin kita harus memindahkannya ke 40 sebagai batas ... Yup, algoritmanya adalah O (1) ) jadi itu tidak masalah "... Inilah sebabnya batas pada input tidak berarti. Fungsinya adalah O (n ^ 5), bukan O (1), dan ini adalah contoh praktis mengapa Big-O tidak tergantung pada batas.

JSobell

2

Sekarang, saya dapat menggunakan hashtable, dan memiliki pencarian O (1) (mengesampingkan implementasi spesifik dari hashtable), tetapi jika saya memiliki eg, daftar, saya akan mencari O (n). Mengingat aksioma ini, keduanya sama jika koleksinya cukup kecil. Tetapi pada titik tertentu mereka berbeda ... apa gunanya?

Praktis, itu adalah titik di mana membangun tabel hash mengambil lebih dari manfaat yang Anda peroleh dari pencarian yang ditingkatkan. Ini akan sangat bervariasi berdasarkan seberapa sering Anda melakukan pencarian, versus seberapa sering Anda melakukan hal-hal lain. O (1) vs O (10) bukan masalah besar jika Anda melakukannya sekali. Jika Anda melakukannya ribuan kali per detik, bahkan itu penting (meskipun setidaknya itu penting pada tingkat yang meningkat secara linear).

Telastyn
sumber

Jika Anda ingin memastikan, lakukan beberapa percobaan untuk melihat struktur data mana yang lebih baik untuk parameter Anda .

Yuval Filmus

@Telastyn Yuval Filmus benar, jika Anda benar-benar ingin memastikan. Saya tahu nama orang Jim, parameternya ok. Tapi dia tidak mendengarkan nasihat seperti itu dari Yuval. Anda harus benar-benar mendengarkan Yuval untuk memastikan dan aman.

InformedA

2

Sementara kutipan itu benar (tetapi tidak jelas) ada juga bahaya untuk itu. Saya juga harus melihat kompleksitas dalam setiap tahap aplikasi Anda.

Terlalu mudah untuk mengatakan: hei saya hanya memiliki daftar kecil, jika saya ingin memeriksa apakah item A ada dalam daftar, saya hanya akan menulis loop mudah untuk melintasi daftar dan membandingkan item.

Kemudian buddyprogrammer Anda datang perlu menggunakan daftar, melihat fungsi Anda dan seperti: hei saya tidak ingin ada duplikat dalam daftar sehingga ia menggunakan fungsi untuk setiap item yang ditambahkan ke daftar.

(Pikiran Anda, ini masih skenario daftar kecil.)

3 tahun kemudian saya datang dan bos saya baru saja melakukan penjualan besar: perangkat lunak kami akan digunakan oleh pengecer nasional besar. Sebelumnya kami hanya melayani toko-toko kecil. Dan sekarang bos saya datang kepada saya bersumpah dan berteriak, mengapa perangkat lunak, yang selalu "bekerja dengan baik" sekarang sangat lambat.

Ternyata, daftar itu adalah daftar klien, dan pelanggan kami hanya memiliki sekitar 100 klien, jadi tidak ada yang memperhatikan. Operasi mengisi daftar pada dasarnya adalah operasi O (1), karena butuh kurang dari satu milidetik. Ya, tidak banyak ketika ada 10.000 klien yang ditambahkan.

Dan bertahun-tahun setelah keputusan O (1) buruk yang asli, perusahaan hampir kehilangan klien besar. Semua karena satu kesalahan desain / asumsi kecil tahun sebelumnya.

Pieter B
sumber

Tetapi juga menggambarkan fitur penting dari banyak sistem dunia nyata: "algoritma" yang Anda pelajari sebagai sarjana sebenarnya adalah bagian dari mana "algoritma" nyata dibuat. Ini biasanya mengisyaratkan; misalnya, kebanyakan orang tahu bahwa quicksort sering ditulis untuk kembali ke jenis penyisipan ketika partisi menjadi cukup kecil, dan pencarian biner sering ditulis untuk kembali ke pencarian linear. Tetapi tidak banyak orang menyadari bahwa jenis gabungan dapat mengambil manfaat dari beberapa pencarian biner.

Nama samaran

1

Motivasi untuk melakukannya didasarkan pada gagasan yang salah bahwa O (1) selalu lebih baik daripada O (lg n), selalu lebih baik daripada O (n). Urutan asimptotik dari operasi hanya relevan jika dalam kondisi realistis ukuran masalah sebenarnya menjadi besar.

Jika saya memiliki dua algoritma dengan waktu ini:

log (n) +10000
n +1

Lalu ada beberapa titik di mana mereka menyeberang. Untuk nlebih kecil dari itu, algoritma "linear" lebih cepat, dan untuk nlebih besar dari itu, algoritma "logaritmik" lebih cepat. Banyak orang membuat kesalahan dengan mengasumsikan algoritma logaritmik lebih cepat, tetapi untuk yang kecil ntidak.

Jika n tetap kecil maka setiap masalah adalah O (1)!

Saya berspekulasi apa yang dimaksudkan di sini adalah bahwa jika nterbatas, maka setiap masalah adalah O (1). Misalnya, jika kami mengurutkan bilangan bulat, kami dapat memilih untuk menggunakan quicksort. O(n*log(n))jelas. Tetapi jika kita memutuskan bahwa tidak mungkin ada lebih dari 2^64=1.8446744e+19bilangan bulat, maka kita tahu bahwa n*log(n)<= 1.8446744e+19*log(1.8446744e+19)<= 1.1805916e+21. Oleh karena itu, algoritme akan selalu memakan waktu kurang dari 1.1805916e+21"satuan waktu". Karena itu adalah waktu yang konstan, kita dapat mengatakan algoritme selalu dapat dilakukan dalam waktu yang konstan itu -> O(1). (Perhatikan bahwa meskipun satuan waktu itu adalah nanodetik, itu adalah total keseluruhan lebih dari 37411 tahun). Tapi tetap saja O(1).

Mooing Duck
sumber

0

Saya menduga banyak dari jawaban ini yang kehilangan konsep mendasar. O (1): O (n) tidak sama dengan f (1): f (n) di mana f adalah fungsi yang sama, karena O tidak mewakili fungsi tunggal. Bahkan grafik bagus Schwern tidak valid karena memiliki sumbu Y yang sama untuk semua garis. Untuk semua menggunakan sumbu yang sama, garis harus fn1, fn2 dan fn3, di mana masing-masing adalah fungsi yang kinerjanya dapat langsung dibandingkan dengan yang lain.

Saya telah mendengar beberapa kali bahwa untuk nilai n yang cukup kecil, O (n) dapat dipikirkan / diperlakukan seolah-olah itu O (1)

Nah, jika n = 1 mereka persis sama? Tidak. Fungsi yang memungkinkan sejumlah variabel iterasi tidak memiliki kesamaan dengan yang tidak, notasi O besar tidak peduli, dan kita juga tidak.

Notasi O besar hanya ada untuk mengekspresikan apa yang terjadi ketika kita memiliki proses berulang, dan bagaimana kinerja (waktu atau sumber daya) akan menurun ketika 'n' meningkat.

Jadi untuk menjawab pertanyaan yang sebenarnya ... Saya akan mengatakan bahwa mereka yang membuat klaim itu tidak memahami notasi Big-O dengan benar, karena ini adalah perbandingan yang tidak masuk akal.

Inilah pertanyaan yang serupa: Jika saya mengulang-ulang serangkaian karakter, dan saya tahu bahwa secara umum string saya akan kurang dari 10 karakter, dapatkah saya mengatakan bahwa itu setara dengan O (1), tetapi jika string saya lebih panjang maka saya akan mengatakan itu O (n)?

Tidak, karena string 10 karakter membutuhkan 10 kali lebih lama dari string 1 karakter, tetapi 100 kali lebih kecil dari string 1000 karakter! Ini O (n).

JSobell
sumber

O (1)

$O(1)$

f (i)

$f(i)$

i

$i$

max {f (0), \dots, f (10)}

$\max\,\{f(0), \dots, f(10)\}$

O (1)

$O(1)$

Ya, dan ini adalah contoh di mana notasi Big-O umumnya disalahpahami. Menurut argumen Anda, jika saya tahu bahwa nilai maksimum n adalah 1.000.000, maka fungsi saya adalah O (1). Bahkan, fungsi saya bisa paling baik O (1) dan paling buruk O (n). Notasi ini digunakan untuk menggambarkan kompleksitas algoritmik, bukan implementasi konkret, dan kami selalu menggunakan yang paling mahal untuk menggambarkan skenario, bukan yang terbaik. Faktanya, menurut argumen Anda, setiap fungsi tunggal yang memungkinkan n <2 adalah O (1)! :)

JSobell

Tidak. Notasi O besar digunakan untuk menggambarkan tingkat pertumbuhan fungsi. Fungsi-fungsi itu bisa digunakan untuk mengukur apa saja. Dan saya pasti tidak berpendapat bahwa "setiap fungsi yang memungkinkan [apa pun artinya itu] adalah ." Saya sebenarnya berpendapat bahwa setiap fungsi yang memiliki properti yang untuk semua adalah , yang benar.

n < 2

$n<2$

O (1)

$O(1)$

f (n) \leq f (10)

$f(n)\leq f(10)$

n

$n$

O (1)

$O(1)$

David Richerby

Maaf, tetapi jika Anda mengatakan bahwa mengetahui batas atas n membuat fungsi O (1), maka Anda mengatakan bahwa representasi notasi terkait langsung dengan nilai n, dan bukan. Segala sesuatu yang Anda sebutkan adalah benar, tetapi menyarankan bahwa karena n memiliki batas maka O (1) tidak benar. Dalam praktiknya ada tempat-tempat di mana apa yang Anda gambarkan dapat diamati, tetapi kami melihat notasi Big-O di sini, bukan pengkodean fungsional. Jadi sekali lagi, mengapa Anda menyarankan bahwa n memiliki maks 10 akan membuatnya O (1)? Kenapa 10? Mengapa tidak 65535, atau 2 ^ 64?

JSobell

Karena itu, jika Anda menulis fungsi yang merangkai string hingga 10 karakter, maka selalu loop atas string, maka itu adalah O (1) karena n selalu 10 :)

JSobell

0

Saya percaya teks yang Anda kutip cukup tidak akurat (menggunakan kata "lebih baik" biasanya tidak ada artinya kecuali Anda memberikan konteksnya: dalam hal waktu, ruang, dll.) Bagaimanapun, saya percaya penjelasan paling sederhana adalah:

Jika waktu eksekusi tumbuh dengan ukuran input maka sudah pasti bukan dan itu harus jelas. tidak berarti cepat . Ini hanya berarti (dalam hal kompleksitas waktu) bahwa waktu eksekusi memiliki batas atas yang konstan . $O(1)$ $O(1)$

Sekarang, mari kita ambil 10 elemen yang relatif kecil dan memiliki beberapa algoritma untuk mengurutkannya (hanya sebuah contoh). Mari kita asumsikan bahwa kita menyimpan elemen dalam struktur yang juga menyediakan kita dengan algoritma yang mampu mengurutkan elemen dalam waktu yang konstan. Katakanlah algoritma sorting kami dapat memiliki kompleksitas berikut (dengan notasi O-besar):

$O(1)$
$O(n)$
$O(nlog(n))$
$O(n^2)$

Algoritme apa yang akan Anda pilih? Jawaban pertama yang terlintas dalam pikiran mungkin "tentu saja saya akan menggunakan satu!", Tetapi ini belum tentu benar. Apa yang Anda lupa ketika berpikir seperti itu adalah bahwa notasi-O besar menyembunyikan faktor konstan . Dan jika Anda tahu perangkat Anda cukup kecil, maka faktor konstan ini mungkin jauh lebih penting daripada kompleksitas asimptotik. $O(1)$

Sekarang mari kita "mengungkapkan" kompleksitas sebenarnya dari algoritma pengurutan yang disebutkan di atas (di mana "benar" berarti tidak menyembunyikan konstanta), diwakili oleh sejumlah langkah yang diperlukan untuk menyelesaikan (dan menganggap semua langkah mengambil jumlah waktu yang sama):

$200$ langkah
$11n$ langkah
$4nlog(n)$ langkah (log dengan basis 2)
$1n^2$ langkah

Jika input kami berukuran 10, maka ini adalah jumlah langkah yang tepat untuk setiap algoritma yang disebutkan di atas:

$200$ langkah
$11 \times 10 = 110$ langkah
$4 \times 10 \times 3.32 \approx 134$ langkah
$1 \times 100 = 100$ langkah

Seperti yang Anda lihat, dalam hal ini algoritma yang tampaknya paling buruk dengan kompleksitas asimptotik adalah yang tercepat, mengalahkan algoritma dengan kompleksitas asimptotik dan . Faktor konstan yang disembunyikan oleh notasi O besar penting di sini. Menurut pendapat saya itu tidak berarti bahwa kita dapat memperlakukan lebih baik daripada (apa artinya itu?) Itu berarti bahwa untuk input yang cukup kecil (seperti yang Anda lihat dalam contoh) mungkin masih lebih cepat daripada karena konstanta tersembunyi. Dan jika konstanta relatif besar dibandingkan dengan ukuran input, itu mungkin lebih penting daripada kompleksitas asimptotik. $O(n^2)$ $O(1), O(n)$ $O(nlog(n))$ $O(n^2)$ $O(1)$ $O(n^2)$ $O(1)$

3yakuya
sumber

“Untuk nilai n kecil, O (n) dapat diperlakukan seolah-olah O (1)”

Jawaban:

Jika tidak tumbuh, itu O (1)