Notasi theta pada waktu yang konstan. Mengapa kami menggunakan angka 1?

9

Dalam notasi asimptotik ketika dinyatakan bahwa jika ukuran masalahnya cukup kecil (misalnya n<cuntuk beberapa konstanta c) solusinya membutuhkan waktu yang konstan dan dituliskan sebagai Theta(1).
Mengapa kami menulis 1 di dalamnya Theta?
Apa 1artinya? Mengapa tidak Theta(c)?

algorithms big-theta pengguna10326
sumber

Jawaban:

8

Notasi-notasi itu dimaksudkan untuk menunjukkan pertumbuhan asimptotik. Konstanta tidak tumbuh dan karena itu cukup sama dengan konstanta yang Anda pilih. Namun, ada konvensi yang Anda pilih 1 untuk menunjukkan tidak ada pertumbuhan.

Saya berasumsi bahwa ini adalah karena Anda ingin menyederhanakan istilah matematika yang dimaksud. Ketika Anda memiliki faktor konstan, hanya bagi dengan itu dan semua yang tersisa adalah 1. Ini membuat perbandingan lebih mudah.

Contoh:

O (34 * n ^ 2) = O (1 * n ^ 2) = O (n ^ 2)

dan

O (2567.2343 * n ^ 2/5) = O (n ^ 2)

Lihat apa yang saya maksud? Karena istilah matematika ini menjadi semakin rumit, Anda tidak ingin memiliki konstanta yang berisik ketika tidak relevan dengan informasi yang Anda minati. Mengapa saya harus menulis O (2342.4534675767) ketika istilah itu dapat lebih mudah diekspresikan dengan O (1), yang mengkomunikasikan fakta-fakta dari kasus ini dengan jelas.

Lebih jauh, artikel wikipedia tentang kompleksitas waktu juga menyiratkan itu adalah konvensi:

Algoritma dikatakan sebagai waktu konstan (juga ditulis sebagai O (1) waktu) ...

Elang
sumber
Saya mengerti. Tapi mengapa tidak hanya Theta (c) yang mencakup konstanta? Ini hanya sebuah konvensi?
user10326
8
@ user10326: Saya pikir itu karena "c" bisa disalahartikan, Anda jelas harus menyatakan bahwa itu adalah konstanta sementara "1" melakukan pekerjaan yang sama secara jelas.
Falcon
Jadi angka sebenarnya tidak relevan? Kami menggunakan 1 bukannya 5 sebagai konvensi?
user10326
1
@ user10326: Ya, karena tidak ada bedanya. Tetapi saya tidak akan menggunakan "0" karena itu dapat menyebabkan banyak kebingungan.
Falcon
@ user10326: Falcon jawabannya masuk akal bukan? jika itu menjadi 5 bukannya 1, menjatuhkan 5 O(5 * n^2)akan terasa kurang alami, sedangkan menjatuhkan * 1adalah matematika dasar.
Steven Jeuris
13

Ini semua sangat bergelombang, tetapi ada alasan matematika mengapa kita tidak menggunakan Theta (c) dan sebaliknya menggunakan Theta (1). Saya akan menggunakan notasi O Besar untuk menunjukkan ini.

Ini ada hubungannya dengan properti notasi Big Theta (juga Big O dan Big Omega). Jika Anda memiliki fungsi dengan tingkat pertumbuhan O(g(x))dan yang lainnya dengan tingkat pertumbuhan di O(c * g(x))mana cbeberapa konstan, Anda akan mengatakan mereka memiliki tingkat pertumbuhan yang sama. Itu adalahO(c * g(x)) = O(g(x))

Kita dapat mengatakan ini karena definisi notasi O Besar ( f(x) = O(g(x))) berarti bahwa kita memiliki fungsi f(x)dan fungsi g(x)sedemikian rupa sehingga |f(x)| <= k * |g(x)|untuk beberapa nilai konstan kdan cukup besar x. Ketika mengalikan dengan konstanta c, kita akan memiliki:

O(c * g(x)) => k * |c * g(x)| = k * |c| * |g(x)| <= k' * g(x) dimana k' = k * |c|

Perhatikan bahwa |k' * g(x)| <= k'' g(x)untuk beberapa nilai konstan k''dan cukup besar x, yang berarti k' * g(x)tumbuh pada laju O(g(x))dan karenanyaO(c * g(x)) = O(g(x))

Ketika g(x) = 1, kita memiliki O(1)pertumbuhan, mengatakan O(c)pertumbuhan untuk beberapa nilai ctidak memberi tahu kita apa-apa karena konstanta sudah diperhitungkan dalam definisi notasi O Besar. DisederhanakanO(c) = O(1)

Jay Lindquist
sumber
3

Ya, tentu saja Anda bisa menulis Theta (c) (atau O (c)) tetapi mengapa itu berbeda dari Theta (n)? n hanyalah variabel yang menunjukkan ukuran input. Anda bisa menulis "Fungsinya adalah Theta (c) di mana c adalah konstanta". Tambahan penting adalah ... di mana c adalah konstanta . Anda harus secara eksplisit menyatakan bahwa pengidentifikasi bukan variabel.

Pertimbangkan teori grafik di mana batas untuk suatu algoritma sering digambarkan sebagai fungsi | V | dan | E |, atau jumlah simpul dan tepi, masing-masing. Maka mungkin lebih bijaksana untuk menyatakan "Fungsinya adalah Theta (| V | * | E | ^ 2)".

Namun Theta (1) selalu konstan - dengan asumsi praktik matematika normal.

Maks
sumber
Theta(1) however is always a constant.Ini adalah bagian yang tidak saya dapatkan.Teta (c) selalu merupakan konstanta juga.Tepat? Jadi saya bertanya-tanya apakah 1memiliki arti khusus
user10326
5
@ user10326: tidak, ctidak selalu merupakan konstanta, karena cmerupakan variabel jika Anda tidak secara eksplisit menyatakan bahwa itu seharusnya ditafsirkan sebagai konstanta ... Yang merupakan perbedaan halus yang dihindari oleh 1.
blubb
Ok, tapi ini mewakili waktu yang konstan.
user10326
2
@ user10326: Tidak, tidak, ini tidak mewakili waktu yang konstan. Ini mewakili waktu yang tumbuh secara linear dengan c. Itu berbeda , karena Anda memerlukan sesuatu tambahan untuk memaksa nilai c untuk tidak pernah berubah, sedangkan 1 tidak pernah berubah.
jprete
1
@ user10326: Atau, sederhananya: cbukan konstanta; cadalah sebuah surat. Huruf-huruf lain mewakili variabel, bagaimana Anda berharap pembaca mengetahui hal ini tidak baik?
Random832
0

Notasi theta adalah tentang pertumbuhan sebagai fungsi dari beberapa variabel - biasanya n. Jika perlu untuk mengklarifikasi variabel mana yang dimaksudkan, cara untuk menulisnya adalah Theta (n ^ 0). Dari sana itu langkah sederhana untuk menerapkan identitas n ^ 0 = 1 (untuk n! = 0).

Peter Taylor
sumber
Tetapi mengapa Anda mengatakan n^0untuk menunjukkan waktu yang konstan dan tidak n^1dalam contoh Anda?
user10326
@ user10326, karena n ^ 1 = n tidak konstan. Tumbuh secara linear.
Peter Taylor
0

O ( c ) secara khusus berarti bahwa kelas algoritma yang terkait tumbuh secara linier dengan c , di mana c adalah ukuran input ke algoritma atau parameter ke algoritma . Bukan c yang sama yang digunakan untuk menjelaskan notasi-O, karena c itu hanya relevan dengan penjelasan, bukan penggunaannya. O ( c ) berisi c yang berbeda yang harus berasal dari konteks input algoritma.

jprete
sumber