Apakah ada algoritma O (1 / n)?

Apakah ada algoritma O (1 / n)?

Atau apa pun yang kurang dari O (1)?

Pertanyaan ini tidak sebodoh kelihatannya. Setidaknya secara teoritis, sesuatu seperti O (1 / n ) sepenuhnya masuk akal ketika kita mengambil definisi matematika dari notasi O Besar :

Sekarang Anda dapat dengan mudah mengganti g ( x ) dengan 1 / x ... sudah jelas bahwa definisi di atas masih berlaku untuk beberapa f .

Untuk tujuan memperkirakan pertumbuhan run-time asimptotik, ini kurang layak ... algoritma yang bermakna tidak bisa lebih cepat ketika input tumbuh. Tentu, Anda dapat membuat algoritma arbitrer untuk memenuhi hal ini, misalnya yang berikut:

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

Jelas, fungsi ini menghabiskan lebih sedikit waktu karena ukuran input tumbuh ... setidaknya sampai batas tertentu, ditegakkan oleh perangkat keras (ketepatan angka, waktu minimum yang sleepbisa menunggu, waktu untuk memproses argumen dll.): Batas ini kemudian akan menjadi batas bawah konstan sehingga sebenarnya fungsi di atas masih memiliki runtime O (1).

Tapi ada yang sebenarnya algoritma dunia nyata di mana runtime dapat menurunkan (setidaknya sebagian) ketika ukuran masukan meningkat. Perhatikan bahwa algoritma ini tidak akan menampilkan perilaku runtime di bawah O (1). Meski begitu, mereka menarik. Misalnya, ambil algoritma pencarian teks yang sangat sederhana oleh Horspool . Di sini, runtime yang diharapkan akan berkurang karena panjang pola pencarian meningkat (tetapi meningkatnya panjang tumpukan jerami akan sekali lagi meningkatkan runtime).

Iya.

Tepatnya ada satu algoritma dengan runtime O (1 / n), algoritma "kosong".

Untuk suatu algoritma menjadi O (1 / n) berarti bahwa ia dijalankan secara asimptotik dalam langkah-langkah yang lebih sedikit daripada algoritma yang terdiri dari satu instruksi. Jika dijalankan dalam langkah kurang dari satu langkah untuk semua n> n0, itu harus terdiri dari tepat tidak ada instruksi sama sekali untuk mereka n. Karena memeriksa 'jika n> n0' memerlukan biaya setidaknya 1 instruksi, itu harus terdiri dari tidak ada instruksi untuk semua n.

Kesimpulannya: Satu-satunya algoritma yang O (1 / n) adalah algoritma kosong, yang terdiri dari tanpa instruksi.

sharptooth benar, O (1) adalah kinerja terbaik. Namun, itu tidak menyiratkan solusi cepat, hanya solusi waktu tetap.

Varian yang menarik, dan mungkin apa yang sebenarnya disarankan, adalah masalah mana yang lebih mudah seiring pertambahan populasi. Saya dapat memikirkan 1, meskipun dibuat-buat dan jawaban yang tidak jelas:

Apakah ada dua orang dalam satu set yang berulang tahun yang sama? Ketika n melebihi 365, kembalikan benar. Meskipun kurang dari 365, ini adalah O (n ln n). Mungkin bukan jawaban yang bagus karena masalahnya tidak perlahan menjadi lebih mudah tetapi hanya menjadi O (1) untuk n> 365.

Itu tidak mungkin. Definisi Big-O adalah yang tidak lebih besar dari ketimpangan:

A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)

Jadi B (n) sebenarnya adalah nilai maksimum, oleh karena itu jika menurun ketika n meningkatkan estimasi tidak akan berubah.

Dari pembelajaran saya sebelumnya tentang notasi O besar, bahkan jika Anda memerlukan 1 langkah (seperti memeriksa variabel, melakukan tugas), yaitu O (1).

Perhatikan bahwa O (1) sama dengan O (6), karena "konstan" tidak masalah. Itu sebabnya kami mengatakan O (n) sama dengan O (3n).

Jadi, jika Anda memerlukan 1 langkah saja, itu O (1) ... dan karena program Anda setidaknya membutuhkan 1 langkah, algoritma minimum yang bisa digunakan adalah O (1). Kecuali jika kita tidak melakukannya, maka itu adalah O (0), saya pikir? Jika kita melakukan apa saja, maka itu adalah O (1), dan itu adalah minimum yang bisa dilakukan.

(Jika kita memilih untuk tidak melakukannya, maka itu bisa menjadi pertanyaan Zen atau Tao ... dalam bidang pemrograman, O (1) masih minimum).

Atau bagaimana dengan ini:

programmer : boss, saya menemukan cara untuk melakukannya dalam waktu O (1)!
Bos : tidak perlu melakukannya, kami bangkrut pagi ini.
programmer : oh lalu, itu menjadi O (0).

Tidak, ini tidak mungkin:

Karena n cenderung tak terhingga dalam 1 / n kita akhirnya mencapai 1 / (inf), yang secara efektif 0.

Dengan demikian, kelas big-oh dari masalahnya adalah O (0) dengan n besar, tetapi lebih dekat ke waktu konstan dengan n rendah. Ini tidak masuk akal, karena satu-satunya hal yang dapat dilakukan lebih cepat daripada waktu konstan adalah:

void nothing() {};

Dan bahkan ini bisa diperdebatkan!

Segera setelah Anda menjalankan perintah, Anda berada di setidaknya O (1), jadi tidak, kami tidak dapat memiliki kelas besar oh (1 / n)!

Bagaimana dengan tidak menjalankan fungsi sama sekali (NOOP)? atau menggunakan nilai tetap. Apakah itu penting?

Saya sering menggunakan O (1 / n) untuk menggambarkan probabilitas yang semakin kecil ketika input semakin besar - misalnya, probabilitas bahwa koin yang adil muncul di log2 (n) membalik adalah O (1 / n).

O (1) berarti "waktu konstan".

Saat Anda menambahkan jalan keluar awal ke loop [1] Anda (dalam notasi O besar) mengubah algoritma O (1) menjadi O (n), tetapi membuatnya lebih cepat.

Caranya secara umum algoritma waktu konstan adalah yang terbaik, dan linear lebih baik daripada eksponensial, tetapi untuk sejumlah kecil n, algoritma eksponensial sebenarnya mungkin lebih cepat.

1: Dengan asumsi panjang daftar statis untuk contoh ini

Bagi siapa pun yang membaca pertanyaan ini dan ingin memahami tentang apa pembicaraan itu, ini mungkin membantu:

|    |constant |logarithmic |linear|  N-log-N |quadratic|  cubic  |  exponential  |
|  n |  O(1)   | O(log n)   | O(n) |O(n log n)|  O(n^2) |  O(n^3) |     O(2^n)    |
|  1 |       1 |          1 |     1|         1|        1|       1 |             2 |
|  2 |       1 |          1 |     2|         2|        4|       8 |             4 |
|  4 |       1 |          2 |     4|         8|       16|      64 |            16 |
|  8 |       1 |          3 |     8|        24|       64|     512 |           256 |
| 16 |       1 |          4 |    16|        64|      256|   4,096 |         65536 |
| 32 |       1 |          5 |    32|       160|    1,024|  32,768 | 4,294,967,296 |
| 64 |       1 |          6 |    64|       384|    4,069| 262,144 |   1.8 x 10^19 |

Saya percaya algoritma kuantum dapat melakukan banyak komputasi "sekaligus" melalui superposisi ...

Saya ragu ini adalah jawaban yang berguna.

banyak orang memiliki jawaban yang benar (Tidak) Berikut cara lain untuk membuktikannya: Untuk memiliki fungsi, Anda harus memanggil fungsi tersebut, dan Anda harus mengembalikan jawaban. Ini membutuhkan jumlah waktu tertentu yang konstan. BAHKAN JIKA sisa pemrosesan memakan waktu lebih sedikit untuk input yang lebih besar, mencetak jawabannya (yang dapat kita asumsikan sebagai bit tunggal) membutuhkan setidaknya waktu yang konstan.

Jika solusi ada, itu dapat disiapkan dan diakses dalam waktu konstan = segera. Misalnya menggunakan struktur data LIFO jika Anda tahu permintaan penyortiran adalah untuk urutan terbalik. Kemudian data sudah disortir, mengingat bahwa model yang sesuai (LIFO) dipilih.

Masalah mana yang lebih mudah seiring pertambahan populasi? Satu jawaban adalah hal seperti bittorrent di mana kecepatan unduhan adalah fungsi terbalik dari jumlah node. Berlawanan dengan mobil, yang semakin melambat saat Anda memuatnya, jaringan berbagi file seperti bittorrent mempercepat semakin banyak node yang terhubung.

Anda tidak bisa pergi di bawah O (1), namun O (k) di mana k kurang dari N adalah mungkin. Kami menyebutnya algoritma waktu sublinear . Dalam beberapa masalah, algoritma waktu Sublinear hanya dapat memberikan solusi perkiraan untuk masalah tertentu. Namun, kadang-kadang, solusi perkiraan baik-baik saja, mungkin karena dataset terlalu besar, atau itu terlalu mahal secara komputasi untuk menghitung semua.

Bagaimana dengan ini:

void FindRandomInList(list l)
{
    while(1)
    {
        int rand = Random.next();
        if (l.contains(rand))
            return;
    }
}

saat ukuran daftar bertambah, runtime yang diharapkan dari program berkurang.

O (1 / n) tidak kurang dari O (1), itu pada dasarnya berarti bahwa semakin banyak data yang Anda miliki, semakin cepat algoritma berjalan. Katakanlah Anda mendapatkan array dan selalu mengisinya hingga 10 ¹⁰⁰ elemen jika memiliki kurang dari itu dan tidak melakukan apa pun jika ada lagi. Yang ini bukan O (1 / n) tentu saja tetapi sesuatu seperti O (-n) :) Notasi O-besar yang terlalu buruk tidak memungkinkan nilai negatif.

Seperti yang telah ditunjukkan, terlepas dari kemungkinan pengecualian dari fungsi null, tidak ada O(1/n)fungsi, karena waktu yang dibutuhkan harus mendekati 0.

Tentu saja, ada beberapa algoritma, seperti yang didefinisikan oleh Konrad, yang sepertinya harus kurang dari O(1)setidaknya dalam beberapa hal.

def get_faster(list):
    how_long = 1/len(list)
    sleep(how_long)

Jika Anda ingin menyelidiki algoritma ini, Anda harus menentukan pengukuran asimptotik Anda sendiri, atau gagasan waktu Anda sendiri. Misalnya, dalam algoritme di atas, saya dapat mengizinkan penggunaan sejumlah operasi "bebas" dalam jumlah tertentu. Dalam algoritma di atas, jika saya mendefinisikan t 'dengan mengecualikan waktu untuk semuanya kecuali tidur, maka t' = 1 / n, yaitu O (1 / n). Mungkin ada contoh yang lebih baik, karena perilaku asimptotiknya sepele. Bahkan, saya yakin bahwa seseorang di luar sana dapat datang dengan indera yang memberikan hasil yang tidak sepele.

Sebagian besar sisa jawaban menafsirkan big-O secara eksklusif tentang waktu berjalan suatu algoritma. Tetapi karena pertanyaannya tidak menyebutkannya, saya pikir layak menyebutkan aplikasi big-O lainnya dalam analisis numerik, yaitu tentang kesalahan.

Banyak algoritma dapat berupa O (h ^ p) atau O (n ^ {- p}) tergantung pada apakah Anda berbicara tentang ukuran langkah (h) atau jumlah divisi (n). Misalnya, dalam metode Euler , Anda mencari perkiraan y (h) mengingat Anda tahu y (0) dan dy / dx (turunan dari y). Perkiraan Anda dari y (h) lebih akurat, semakin dekat h ke 0. Jadi untuk menemukan y (x) untuk beberapa x sewenang-wenang, seseorang mengambil interval 0 hingga x, membaginya hingga n buah, dan menjalankan metode Euler di setiap titik, untuk beralih dari y (0) ke y (x / n) ke y (2x / n), dan seterusnya.

Jadi metode Euler kemudian merupakan algoritma O (h) atau O (1 / n), di mana h biasanya ditafsirkan sebagai ukuran langkah dan n ditafsirkan sebagai berapa kali Anda membagi interval.

Anda juga dapat memiliki O (1 / jam) dalam aplikasi analisis numerik nyata, karena kesalahan pembulatan titik mengambang . Semakin kecil interval yang Anda buat, semakin banyak pembatalan yang terjadi untuk penerapan algoritma tertentu, lebih banyak kehilangan digit signifikan, dan karenanya lebih banyak kesalahan, yang akan disebarkan melalui algoritma.

Untuk metode Euler, jika Anda menggunakan floating point, gunakan langkah dan pembatalan yang cukup kecil dan Anda menambahkan angka kecil ke angka besar, meninggalkan angka besar tidak berubah. Untuk algoritma yang menghitung turunan melalui pengurangan satu sama lain dua angka dari fungsi yang dievaluasi pada dua posisi yang sangat dekat, kira-kira y '(x) dengan (y (x + h) - y (x) / h), dalam fungsi yang halus y (x + h) mendekati y (x) yang menghasilkan pembatalan besar dan estimasi untuk turunan dengan angka signifikan yang lebih sedikit. Ini pada gilirannya akan merambat ke algoritma apa pun yang Anda perlukan untuk turunannya (misalnya, masalah nilai batas).

OK, saya sedikit memikirkannya, dan mungkin ada algoritma yang bisa mengikuti bentuk umum ini:

Anda perlu menghitung masalah salesman keliling untuk grafik 1000 simpul, namun, Anda juga diberikan daftar node yang tidak dapat Anda kunjungi. Ketika daftar node yang tidak dapat dibalik semakin besar, masalahnya menjadi lebih mudah untuk dipecahkan.

Saya melihat algoritma yang O (1 / n) diakui untuk batas atas:

Anda memiliki serangkaian input besar yang berubah karena sesuatu di luar rutinitas (mungkin merefleksikan perangkat keras atau bahkan mungkin beberapa inti lain dalam prosesor yang melakukannya.) Dan Anda harus memilih yang acak tetapi valid.

Sekarang, jika itu tidak berubah Anda hanya akan membuat daftar item, pilih satu secara acak dan dapatkan O (1) waktu. Namun, sifat dinamis dari data menghalangi pembuatan daftar, Anda hanya perlu menyelidiki secara acak dan menguji validitas penyelidikan. (Dan perhatikan bahwa secara inheren tidak ada jaminan jawabannya masih valid ketika dikembalikan. Ini masih bisa menggunakan - katakanlah, AI untuk unit dalam permainan. Bisa menembak pada target yang keluar dari pandangan saat itu menarik pelatuknya.)

Ini memiliki kinerja kasus tak terbatas terburuk tetapi kinerja kasus rata-rata yang turun saat ruang data terisi.

Dalam analisis numerik, algoritma aproksimasi harus memiliki kompleksitas asimtotik sub-konstan dalam toleransi aproksimasi.

class Function
{
    public double[] ApproximateSolution(double tolerance)
    {
        // if this isn't sub-constant on the parameter, it's rather useless
    }
}

Saya kira kurang dari O (1) tidak mungkin. Setiap waktu yang diambil oleh algo disebut sebagai O (1). Tetapi untuk O (1 / n) bagaimana dengan fungsi di bawah ini. (Saya tahu ada banyak varian yang telah disajikan dalam solusi ini, tapi saya kira mereka semua memiliki beberapa kekurangan (tidak utama, mereka menjelaskan konsep dengan baik). Jadi di sini ada satu, hanya demi argumen:

def 1_by_n(n, C = 10):   #n could be float. C could be any positive number
  if n <= 0.0:           #If input is actually 0, infinite loop.
    while True:
      sleep(1)           #or pass
    return               #This line is not needed and is unreachable
  delta = 0.0001
  itr = delta
  while delta < C/n:
    itr += delta

Jadi dengan bertambahnya fungsi akan memakan waktu lebih sedikit dan lebih sedikit. Juga dipastikan bahwa jika input benar-benar 0, maka fungsi akan membutuhkan waktu lama untuk kembali.

Orang mungkin berpendapat bahwa itu akan dibatasi oleh presisi mesin. Jadi, sinc memiliki batas atas yaitu O (1). Tapi kita juga bisa memotongnya, dengan mengambil input n dan C dalam string. Dan penambahan dan perbandingan dilakukan pada string. Gagasannya adalah, dengan ini kita dapat mengurangi n sembarang kecil. Jadi batas atas fungsi tidak dibatasi, bahkan ketika kita abaikan n = 0.

Saya juga percaya bahwa kita tidak bisa hanya mengatakan bahwa run time adalah O (1 / n). Tetapi kita harus mengatakan sesuatu seperti O (1 + 1 / n)

Dimungkinkan untuk membuat algoritma yang O (1 / n). Salah satu contoh akan menjadi loop yang mengulang beberapa kelipatan dari f (n) -n kali di mana f (n) adalah beberapa fungsi yang nilainya dijamin lebih besar dari n dan batas f (n) -n saat n mendekati tak terhingga adalah nol. Perhitungan f (n) juga harus konstan untuk semua n. Saya tidak tahu secara langsung seperti apa f (n) akan terlihat atau aplikasi apa yang akan dimiliki algoritma seperti itu, menurut pendapat saya, namun fungsi seperti itu bisa ada tetapi algoritma yang dihasilkan tidak memiliki tujuan selain untuk membuktikan kemungkinan algoritma dengan O (1 / n).

Saya tidak tahu tentang algoritma tetapi kompleksitas kurang dari O (1) muncul dalam algoritma acak. Sebenarnya, o (1) (sedikit o) kurang dari O (1). Kompleksitas semacam ini biasanya muncul dalam algoritma acak. Sebagai contoh, seperti yang Anda katakan, ketika probabilitas beberapa peristiwa adalah urutan 1 / n mereka menyatakannya dengan o (1). Atau ketika mereka ingin mengatakan bahwa sesuatu terjadi dengan probabilitas tinggi (misalnya 1 - 1 / n) mereka menyatakannya dengan 1 - o (1).

Jika jawabannya sama terlepas dari input data maka Anda memiliki algoritma O (0).

atau dengan kata lain - jawabannya diketahui sebelum input data dikirimkan - fungsinya dapat dioptimalkan - jadi O (0)

Notasi O besar mewakili skenario kasus terburuk untuk suatu algoritma yang tidak sama dengan run time tipikal. Mudah untuk membuktikan bahwa algoritma O (1 / n) adalah algoritma O (1). Menurut definisi,
O (1 / n) -> T (n) <= 1 / n, untuk semua n> = C> 0
O (1 / n) -> T (n) <= 1 / C, Karena 1 / n <= 1 / C untuk semua n> = C
O (1 / n) -> O (1), karena notasi Big-O mengabaikan konstanta (yaitu nilai C tidak masalah)

Tidak ada yang lebih kecil dari O (1) Notasi O-besar menyiratkan urutan kompleksitas terbesar untuk suatu algoritma

Jika suatu algoritma memiliki runtime n ^ 3 + n ^ 2 + n + 5 maka itu adalah O (n ^ 3) Kekuatan yang lebih rendah tidak penting di sini sama sekali karena sebagai n -> Inf, n ^ 2 akan tidak relevan dibandingkan dengan n ^ 3

Demikian juga dengan n -> Inf, O (1 / n) akan tidak relevan dibandingkan dengan O (1) maka 3 + O (1 / n) akan sama dengan O (1) sehingga menjadikan O (1) komputasi sekecil mungkin. kompleksitas

inline void O0Algorithm() {}

Berikut adalah algoritma O (1 / n) sederhana. Dan itu bahkan melakukan sesuatu yang menarik!

function foo(list input) {
  int m;
  double output;

  m = (1/ input.size) * max_value;  
  output = 0;
  for (int i = 0; i < m; i++)
    output+= random(0,1);

  return output;
}

O (1 / n) dimungkinkan karena menggambarkan bagaimana output suatu fungsi berubah mengingat ukuran input yang meningkat. Jika kita menggunakan fungsi 1 / n untuk menggambarkan jumlah instruksi yang dieksekusi fungsi maka tidak ada persyaratan bahwa fungsi mengambil instruksi nol untuk ukuran input apa pun. Sebaliknya, untuk setiap ukuran input, n di atas beberapa ambang batas, jumlah instruksi yang diperlukan dibatasi di atas oleh konstanta positif dikalikan dengan 1 / n. Karena tidak ada angka aktual yang 1 / n adalah 0, dan konstanta adalah positif, maka tidak ada alasan mengapa fungsi akan dibatasi untuk mengambil instruksi 0 atau lebih sedikit.