Waktu polinomial dan waktu eksponensial

90

Bisakah seseorang menjelaskan perbedaan antara algoritma waktu polinomial, waktu bukan polinomial, dan waktu eksponensial?

Misalnya, jika suatu algoritme membutuhkan O (n ^ 2) waktu, lalu masuk dalam kategori apa?

algorithm Abdul Samad
sumber

Jawaban:

85

Lihat ini .

Eksponensial lebih buruk dari polinomial.

O (n ^ 2) termasuk dalam kategori kuadrat, yang merupakan jenis polinomial (kasus khusus eksponen sama dengan 2) dan lebih baik daripada eksponensial.

Eksponensial jauh lebih buruk daripada polinomial. Lihatlah bagaimana fungsinya berkembang

n    = 10    |     100   |      1000

n^2  = 100   |   10000   |   1000000 

k^n  = k^10  |   k^100   |    k^1000

k ^ 1000 sangat besar kecuali k lebih kecil dari sesuatu seperti 1.1. Seperti, sesuatu seperti setiap partikel di alam semesta harus melakukan 100 miliar miliar miliar operasi per detik selama triliunan miliar miliar tahun untuk menyelesaikannya.

Saya tidak menghitungnya, tapi ITU BESAR.

hvgotcodes
sumber
29
Saya menikmati semua ilham Anda.
Josephine
7
k ^ 1000 sangat besar jika k jauh lebih besar dari 1. Jika k = 1 kurang mengesankan, dan jika k = 1.00069387 ..., itu 2.
Josephine
2
Bagaimana dengan n! vs k ^ n. Saya tahu untuk 2 ^ n (paling umum), n! akan lebih mahal, tetapi saya percaya untuk k ^ n umum di mana k> 2, n! akan lebih murah.
Saad
1
Saya senang Anda tidak mengatakan "miliaran dan miliaran". :-)
Tom Russell
@Aad n! akan selalu lebih mahal daripada k ^ n untuk k konstan, tanpa gejala. Anda benar, bagaimanapun, dalam hal ini hanya terjadi setelah kita mencapai nilai n yang tinggi. Dengan pendekatan Stirling, waktu faktorial seharusnya menjadi lebih mahal sekitar ketika n = e * k, di mana e = 2,71828 ..
inavda
136

Berikut adalah beberapa fungsi Big-O umum saat menganalisis algoritme.

  • O ( 1 ) - waktu konstan
  • O ( log (n) ) - waktu logaritmik
  • O ( (log (n)) c ) - waktu polilogaritmik
  • O ( n ) - waktu linier
  • O ( n 2 ) - waktu kuadrat
  • O ( n c ) - waktu polinomial
  • O ( c n ) - waktu eksponensial
  • O ( n! ) - waktu faktorial

(n = ukuran input, c = beberapa konstanta)

Berikut adalah grafik model yang mewakili kompleksitas Big-O dari beberapa fungsi

model grafik

Bersulang :-)

kredit grafik http://bigocheatsheet.com/

Mohanraj Balasubramaniam
sumber
12
Ditambah satu untuk lebih sedikit kata dan lebih jelas.
pengguna3144836
1 = n ^ 0 begitu juga polinomial
BigChief
46

O (n ^ 2) adalah waktu polinomial. Polinomialnya adalah f (n) = n ^ 2. Di sisi lain, O (2 ^ n) adalah waktu eksponensial, di mana fungsi eksponensial yang tersirat adalah f (n) = 2 ^ n. Perbedaannya adalah apakah fungsi dari n menempatkan n di basis eksponen, atau dalam eksponen itu sendiri.

Fungsi pertumbuhan eksponensial apa pun akan tumbuh secara signifikan lebih cepat (jangka panjang) daripada fungsi polinomial apa pun, jadi perbedaannya relevan dengan efisiensi algoritme, terutama untuk nilai n yang besar.

Josephine
sumber
Jawaban ini bersifat otoritatif (baik), tetapi berbeda dengan jawaban @ dheeran, saya yakin, apakah basis dalam kasus eksponensial tentu saja 2. Atau mungkin saya salah paham dan hanya perlu membersihkan aljabar saya.
Tom Russell
21

Waktu polinomial.

Polinomial adalah jumlah suku yang terlihat seperti Constant * x^k Eksponensial artinyaConstant * k^x

(dalam kedua kasus, k adalah konstanta dan x adalah variabel).

Waktu eksekusi algoritme eksponensial tumbuh jauh lebih cepat daripada waktu eksekusi algoritme polinomial.

Sejuk
sumber
18

Eksponensial (Anda memiliki fungsi eksponensial jika MINIMAL ONE EXPONENT bergantung pada parameter):

  • Misalnya f (x) = konstanta ^ x

Polinomial (Anda memiliki fungsi polinomial jika NO EXPONENT bergantung pada beberapa parameter fungsi):

  • Misalnya f (x) = x ^ konstanta
Erhard Dinhobl
sumber
4
Saya tidak suka jika tidak ada dari jawaban asli saya yang tersisa setelah diedit oleh pengguna. Apakah ini semacam "memancing"?
Erhard Dinhobl
2
Saya harus setuju Perubahannya konyol.
satya di rel
3

waktu polinomial O (n) ^ k berarti Jumlah operasi sebanding dengan pangkat k dari ukuran input

waktu eksponensial O (k) ^ n berarti Jumlah operasi sebanding dengan eksponen ukuran input

Siswa
sumber
0

o (n sequre) adalah kompleksitas waktu polinimal sedangkan o (2 ^ n) adalah kompleksitas waktu eksponensial jika p = np ketika kasus terbaik, dalam kasus terburuk p = np tidak sama karena ukuran input n bertambah panjang atau input sizer bertambah begitu Semakin lama semakin buruk penanganannya sehingga kompleksitas laju pertumbuhan meningkat dan bergantung pada n ukuran masukan bila masukan kecil itu polynimal bila ukuran masukan besar dan besar jadi p = np tidak sama artinya tingkat pertumbuhan bergantung pada ukuran masukan "N ". optimasi, sat, klik, dan himpunan independen juga bertemu secara eksponensial hingga polynimal.

nasir
sumber