Apa yang dimaksud dengan "waktu akses O (1)"?

Saya telah melihat istilah "O (1) waktu akses" yang dulu berarti "dengan cepat" tetapi saya tidak mengerti apa artinya. Istilah lain yang saya lihat bersamanya dalam konteks yang sama adalah "O (n) waktu akses". Bisakah seseorang menjelaskan secara sederhana apa arti istilah-istilah ini?

Lihat juga

• Apa itu notasi Big O? Apakah Anda menggunakannya?
• Big-O untuk Anak Usia Delapan Tahun?

Anda akan ingin membaca tentang Urutan kompleksitas.

http://en.wikipedia.org/wiki/Big_O_notation

Singkatnya, O (1) berarti bahwa dibutuhkan waktu yang konstan, seperti 14 nanodetik, atau tiga menit berapa pun jumlah data dalam kumpulan tersebut.

O (n) artinya dibutuhkan sejumlah waktu linier dengan besarnya himpunan, sehingga himpunan yang ukurannya dua kali lipat akan memakan waktu dua kali lipat. Anda mungkin tidak ingin memasukkan jutaan objek ke salah satunya.

Intinya, Ini berarti bahwa dibutuhkan jumlah waktu yang sama untuk mencari nilai dalam koleksi Anda apakah Anda memiliki sejumlah kecil item dalam koleksi Anda atau sangat banyak (dalam batasan perangkat keras Anda)

O (n) berarti waktu yang dibutuhkan untuk mencari item sebanding dengan jumlah item dalam koleksi.

Contoh umum dari ini adalah larik, yang dapat diakses secara langsung, terlepas dari ukurannya, dan daftar tertaut, yang harus dilalui agar dari awal dapat mengakses item tertentu.

Operasi lain yang biasa dibahas adalah penyisipan. Koleksi dapat berupa O (1) untuk akses tetapi O (n) untuk penyisipan. Nyatanya, sebuah array memiliki perilaku yang persis seperti ini, karena untuk menyisipkan item di tengah, Anda harus memindahkan setiap item ke kanan dengan menyalinnya ke slot berikut.

Setiap jawaban yang saat ini menanggapi pertanyaan ini memberi tahu Anda bahwa O(1)waktu konstan rata-rata (apa pun yang terjadi pada pengukuran; bisa jadi runtime, jumlah operasi, dll.). Ini tidak akurat.

Untuk mengatakan bahwa runtime O(1)berarti ada konstanta csedemikian rupa sehingga runtime dibatasi di atas c, tidak tergantung pada input. Misalnya, mengembalikan elemen pertama dari array nbilangan bulat adalah O(1):

int firstElement(int *a, int n) {
    return a[0];
}

Tetapi fungsi ini O(1)juga:

int identity(int i) {
    if(i == 0) {
        sleep(60 * 60 * 24 * 365);
    }
    return i;
}

Runtime di sini dibatasi di atas oleh 1 tahun, tetapi sebagian besar waktu runtime berada pada urutan nanodetik.

Untuk mengatakan bahwa runtime O(n)berarti ada konstanta csedemikian rupa sehingga runtime dibatasi di atas c * n, di mana nmengukur ukuran input. Misalnya, mencari jumlah kemunculan bilangan bulat tertentu dalam larik nbilangan bulat yang tidak diurutkan dengan algoritme berikut adalah O(n):

int count(int *a, int n, int item) {
    int c = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] == item) c++;
    }
    return c;
}

Ini karena kita harus melakukan iterasi melalui larik yang memeriksa setiap elemen satu per satu.

O (1) berarti waktu untuk mengakses sesuatu tidak tergantung pada jumlah item dalam koleksi.

O (N) berarti waktu untuk mengakses item sebanding dengan jumlah (N) item dalam koleksi.

O (1) tidak selalu berarti "cepat". Artinya waktu yang dibutuhkan konstan, dan bukan berdasarkan besar kecilnya input ke fungsi. Konstan bisa cepat atau lambat. O (n) berarti bahwa waktu yang dibutuhkan fungsi akan berubah secara proporsional dengan ukuran input ke fungsi, dilambangkan dengan n. Sekali lagi, ini bisa cepat atau lambat, tetapi akan menjadi lebih lambat seiring bertambahnya ukuran n.

Ini disebut notasi Big O , dan menjelaskan waktu pencarian untuk berbagai algoritme.

O (1) berarti run time kasus terburuk adalah konstan. Untuk sebagian besar situasi, ini berarti Anda tidak benar-benar perlu mencari koleksi, Anda dapat langsung menemukan apa yang Anda cari.

O(1)selalu dieksekusi dalam waktu yang sama terlepas dari dataset n. Contoh dari O (1) adalah ArrayList yang mengakses elemennya dengan index.

O(n)juga dikenal sebagai Linear Order, kinerja akan tumbuh secara linier dan berbanding lurus dengan ukuran data masukan. Contoh dari O (n) akan menjadi penyisipan dan penghapusan ArrayList pada posisi acak. Karena setiap penyisipan / penghapusan berikutnya pada posisi acak akan menyebabkan elemen di ArrayList bergeser ke kiri kanan dari array internalnya untuk mempertahankan struktur liniernya, belum lagi tentang pembuatan array baru dan penyalinan elemen dari yang lama ke array baru yang membutuhkan waktu pemrosesan yang mahal, sehingga merusak kinerja.

"Big O notation" adalah cara untuk mengekspresikan kecepatan algoritma. nadalah jumlah data yang digunakan algoritme. O(1)Artinya, berapa pun banyaknya data, itu akan dieksekusi dalam waktu yang konstan. O(n)artinya sebanding dengan jumlah datanya.

Pada dasarnya, O (1) berarti waktu komputasi konstan, sedangkan O (n) berarti akan bergantung secara linier pada ukuran input - yaitu perulangan melalui array memiliki O (n) - hanya perulangan -, karena tergantung pada jumlahnya jumlah item, sementara menghitung maksimum antara angka biasa memiliki O (1).

Wikipedia mungkin juga membantu: http://en.wikipedia.org/wiki/Computational_complexity_theory

Cara termudah untuk membedakan O (1) dan O (n) adalah membandingkan larik dan daftar.

Untuk array, jika Anda memiliki nilai indeks yang tepat, Anda dapat mengakses datanya secara instan. (Jika Anda tidak mengetahui indeks dan harus melakukan loop melalui array, maka itu tidak akan menjadi O (1) lagi)

Untuk daftar, Anda selalu perlu mengulanginya apakah Anda tahu indeksnya atau tidak.

Berikut ini analogi sederhana; Bayangkan anda sedang mendownload film secara online, dengan O (1), jika perlu waktu 5 menit untuk mendownload satu film, masih membutuhkan waktu yang sama untuk mendownload 20 film. Jadi tidak masalah berapa banyak film yang Anda unduh, itu akan memakan waktu yang sama (5 menit) baik itu satu atau 20 film. Contoh normal dari analogi ini adalah ketika Anda pergi ke perpustakaan film, apakah Anda mengambil satu atau 5 film, Anda hanya akan memilihnya sekaligus. Karenanya menghabiskan waktu yang sama.

Namun demikian, dengan O (n), jika dibutuhkan 5 menit untuk mendownload satu film, dibutuhkan sekitar 50 menit untuk mendownload 10 film. Jadi waktu tidak konstan atau entah bagaimana sebanding dengan jumlah film yang Anda unduh.

Artinya waktu akses konstan. Baik Anda mengakses dari 100 atau 100.000 rekaman, waktu pengambilannya akan sama.

Sebaliknya, waktu akses O (n) akan menunjukkan bahwa waktu pengambilan berbanding lurus dengan jumlah record yang Anda akses.

Artinya akses membutuhkan waktu yang konstan yaitu tidak tergantung pada ukuran dataset. O (n) berarti akses akan bergantung pada ukuran dataset secara linier.

O juga dikenal sebagai O besar.

Pengantar Algoritma: Edisi Kedua oleh Cormen, Leiserson, Rivest & Stein mengatakan di halaman 44 itu

Karena konstanta adalah polinomial derajat-0, kita dapat mengekspresikan fungsi konstanta apa pun sebagai Theta (n ^ 0), atau Theta (1). Namun, notasi terakhir ini adalah penyalahgunaan kecil, karena tidak jelas variabel apa yang cenderung tak terbatas. Kita akan sering menggunakan notasi Theta (1) untuk mengartikan fungsi konstanta atau konstanta sehubungan dengan beberapa variabel. ... Kami menyatakan dengan O (g (n)) ... himpunan fungsi f (n) sedemikian rupa sehingga ada konstanta positif c dan n0 sehingga 0 <= f (n) <= c * g (n) untuk semua n> = n0. ... Perhatikan bahwa f (n) = Theta (g (n)) berarti f (n) = O (g (n)), karena notasi Theta lebih kuat dari notasi O.

Jika suatu algoritme berjalan dalam waktu O (1), itu berarti bahwa secara asimtotik tidak bergantung pada variabel apa pun, artinya ada setidaknya satu konstanta positif yang ketika dikalikan dengan satu lebih besar daripada kompleksitas asimtotik (~ runtime) fungsi untuk nilai n di atas jumlah tertentu. Secara teknis, ini adalah waktu O (n ^ 0).

O (1) berarti Akses Acak. Dalam Memori Akses Acak mana pun, waktu yang dibutuhkan untuk mengakses elemen apa pun di lokasi mana pun adalah sama. Di sini waktu dapat berupa bilangan bulat apa pun, tetapi satu-satunya hal yang perlu diingat adalah waktu yang dibutuhkan untuk mengambil elemen di (n-1) atau lokasi ke-n akan sama (yaitu konstan).

Sedangkan O (n) bergantung pada besarnya n.

Menurut perspektif saya,

O (1) berarti waktu untuk menjalankan satu operasi atau instruksi pada satu waktu adalah satu, dalam analisis kompleksitas waktu algoritma untuk kasus terbaik.