Pemrograman daya: O (1 ^ N), O (N ^ 1), O (2 ^ N), O (N ^ 2) semuanya dalam satu

65

Tulis sebuah program (atau fungsi) yang memperlihatkan empat kompleksitas waktu O besar yang umum tergantung pada cara dijalankannya. Dalam bentuk apa pun yang diperlukan dalam bilangan bulat N positif yang Anda anggap kurang dari 31 .

  1. Ketika program dijalankan dalam bentuk aslinya , ia harus memiliki kompleksitas konstan . Yaitu, kompleksitasnya harus Θ (1) atau, dengan kata lain, Θ (1 ^ N) .

  2. Ketika program dibalik dan dijalankan harus memiliki kompleksitas linier . Artinya, kompleksitasnya harus Θ (N) atau, ekuivalen, Θ (N ^ 1) .
    (Ini masuk akal karena N^1yang 1^Nterbalik.)

  3. Ketika program ini dua kali lipat , yaitu concatenated untuk dirinya sendiri, dan menjalankannya harus memiliki eksponensial kompleksitas, khususnya 2 N . Artinya, kompleksitasnya harus Θ (2 ^ N) .
    (Ini masuk akal karena 2in 2^Nadalah double 1in 1^N.)

  4. Ketika program digandakan dan dibalik dan dijalankan harus memiliki kompleksitas polinomial , khususnya N 2 . Artinya, kompleksitasnya harus Θ (N ^ 2) .
    (Ini masuk akal karena N^2yang 2^Nterbalik.)

Keempat kasus ini adalah satu-satunya yang perlu Anda tangani.

Perhatikan bahwa untuk ketepatan saya menggunakan notasi theta (Θ) besar alih-alih O besar karena runtime program Anda harus dibatasi baik di atas maupun di bawah oleh kompleksitas yang diperlukan. Kalau tidak, hanya menulis fungsi dalam O (1) akan memenuhi keempat poin. Tidak terlalu penting untuk memahami nuansa di sini. Terutama, jika program Anda melakukan operasi k * f (N) untuk beberapa konstanta k maka kemungkinan dalam Θ (f (N)).

Contoh

Jika program aslinya

ABCDE

maka menjalankannya akan membutuhkan waktu yang konstan. Yaitu, apakah input N adalah 1 atau 2147483647 (2 31 -1) atau nilai apa pun di antaranya, ia harus diakhiri dalam jumlah waktu yang kira-kira sama.

Versi program yang dibalik

EDCBA

harus mengambil waktu linier dalam hal N. Artinya, waktu yang dibutuhkan untuk mengakhiri harus sebanding dengan N. Jadi N = 1 membutuhkan waktu paling sedikit dan N = 2147483647 mengambil paling banyak.

Versi program yang berlipat ganda

ABCDEABCDE

harus mengambil dua-to-the-N waktu dalam hal N. Artinya, waktu yang dibutuhkan untuk mengakhiri harus kira-kira sebanding dengan 2 N . Jadi jika N = 1 berakhir dalam waktu sekitar satu detik, N = 60 akan membutuhkan waktu lebih lama dari umur alam semesta untuk berakhir. (Tidak, kamu tidak perlu mengujinya.)

Versi program yang berlipat dan terbalik

EDCBAEDCBA

harus mengambil waktu kuadrat dalam hal N. Artinya, waktu yang diperlukan untuk mengakhiri harus sebanding dengan N * N. Jadi jika N = 1 berakhir dalam sekitar satu detik, N = 60 akan memakan waktu sekitar satu jam untuk berakhir.

Detail

  • Anda perlu menunjukkan atau berargumen bahwa program Anda berjalan dalam kompleksitas yang Anda katakan demikian. Memberikan beberapa data waktu adalah ide yang baik tetapi juga mencoba menjelaskan mengapa secara teoritis kerumitannya benar.

  • Tidak apa-apa jika dalam praktiknya waktu yang diambil program Anda tidak sepenuhnya mewakili kompleksitasnya (atau bahkan deterministik). mis. input N +1 mungkin terkadang berjalan lebih cepat dari N.

  • Lingkungan tempat Anda menjalankan program tidak masalah. Anda dapat membuat asumsi dasar tentang bagaimana bahasa populer tidak pernah secara sengaja membuang waktu dalam algoritme tetapi, misalnya, jika Anda tahu versi Java Anda mengimplementasikan bubble sort daripada algoritma penyortiran yang lebih cepat , maka Anda harus memperhitungkannya jika Anda melakukan penyortiran .

  • Untuk semua kompleksitas di sini asumsikan kita berbicara tentang skenario terburuk , bukan yang terbaik atau rata-rata.

  • Kompleksitas ruang program tidak masalah, hanya kompleksitas waktu.

  • Program dapat menghasilkan apa saja. Yang penting mereka mengambil bilangan bulat positif N dan memiliki kompleksitas waktu yang tepat.

  • Komentar dan program multiline diizinkan. (Anda dapat menganggap \r\nterbalik \r\nuntuk kompatibilitas Windows.)

Pengingat O Besar

Dari tercepat ke paling lambat itu O(1), O(N), O(N^2), O(2^N)(urutan 1, 2, 4, 3 di atas).

Istilah yang lebih lambat selalu mendominasi, mis O(2^N + N^2 + N) = O(2^N).

O(k*f(N)) = O(f(N))untuk konstanta k. Jadi O(2) = O(30) = O(1)dan O(2*N) = O(0.1*N) = O(N).

Ingat O(N^2) != O(N^3)dan O(2^N) != O(3^N).

Lembar contekan O yang besar dan rapi.

Mencetak gol

Ini adalah kode golf normal. Program asli terpendek (waktu konstan) dalam byte menang.

code-golf integer source-layout restricted-complexity set-theory Hobi Calvin
sumber
Pertanyaan yang sangat bagus! Poin minor: kita tidak harus menentukan kasus terburuk / kasus terbaik / rata-rata, karena satu-satunya input yang dihitung sebagai ukuran N adalah angka N itu sendiri (yang BTW bukanlah gagasan umum tentang ukuran input: yang akan memperlakukan input N sebagai ukuran log N). Jadi hanya ada satu kasus untuk setiap N, yang secara bersamaan merupakan kasus terbaik, terburuk, dan rata-rata.
ShreevatsaR
5
Tampaknya Anda telah menyimpang dari definisi kompleksitas yang biasa. Kami selalu mendefinisikan kompleksitas waktu dari suatu algoritma sebagai fungsi dari ukuran inputnya . Dalam kasus di mana input adalah angka, ukuran input adalah basis-2 logaritma dari angka itu. Jadi program n = input(); for i in xrange(n): passmemiliki kompleksitas eksponensial, karena dibutuhkan 2 ** klangkah - langkah, di mana k = log_2(n)ukuran inputnya. Anda harus mengklarifikasi apakah ini masalahnya, karena secara dramatis mengubah persyaratan.
wchargin

Jawaban:

36

Python 3 , 102 byte

try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt

Cobalah online!

Ini dari O (1 ^ n), karena inilah yang dilakukan oleh program:

  • mengevaluasi input
  • buat array [0]
  • cetak ini

Terbalik:


try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt

Cobalah online!

Ini dari O (n ^ 1), karena ini yang dilakukan oleh program:

  • mengevaluasi input
  • buat array [0] * input (0 diulang sebanyak input)
  • cetak ini

Dua kali lipat:

try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt
try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt

Cobalah online!

Ini dari O (2 ^ n), karena inilah yang dilakukan oleh program:

  • mengevaluasi input
  • buat array [0]
  • cetak ini
  • cobalah untuk mengevaluasi input
  • gagal
  • buat array [0] * (2 ^ input) (0 diulang sebanyak 2 ^ input)
  • cetak ini

Berganda dan terbalik:


try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt
try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt

Cobalah online!

Ini dari O (n ^ 2), karena inilah yang dilakukan oleh program:

  • mengevaluasi input
  • buat array [0] * input (0 diulang sebanyak input)
  • cetak ini
  • cobalah untuk mengevaluasi input
  • gagal
  • buat array [0] * (input ^ 2) (0 diulang sebanyak input kuadrat)
  • cetak ini
Biarawati Bocor
sumber
Mengapa tidak menunggu interaksi pengguna saat ada beberapa panggilan input()?
Jonathan Allan
1
Ini adalah celah bahwa "ujung transmisi" ditransmisikan pada akhir transmisi?
Leaky Nun
1
Bisakah Anda menjelaskannya?
Brain Guider
1
Re: "akhir file" argumen, Anda melihat hal-hal yang mundur. Saat Anda menggunakan terminal, permintaan untuk input hang karena ada sesuatu yang terhubung dengannya; ctrl-D dapat dikirim untuk secara eksplisit mengirim tidak ada input. Jika input terhubung ke file kosong (seperti TIO lakukan jika Anda membiarkan kotak input kosong), atau jika terhubung ke file di mana semua input telah dibaca, tidak perlu permintaan input untuk melakukan apa pun; sudah tahu tidak ada input. Pada UNIX / Linux, "akhir file" dan "tidak ada input" tidak dapat dibedakan pada file biasa.
3
Untuk kasus pertama, kapakah input, dan lsatu, jadi Anda masih menghitung 1**k, kan? Yang mana yang perlu O(log(k))waktu, terlepas dari kenyataan bahwa Anda dan saya dan semua orang sudah tahu sebelumnya bahwa itu adalah satu?
Richard Rast
18

Perl 5, 82 73 71 +1 + (untuk -n flag) = 72 byte

Saya yakin saya bisa bermain golf ini (lebih banyak) lebih banyak, tetapi ini adalah waktu tidur, saya telah menghabiskan cukup banyak waktu debugging, dan saya bangga dengan apa yang saya miliki sejauh ini.

#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;

Program itu sendiri tidak menggunakan input, dan hanya mengevaluasi string yang dimulai dengan komentar dan kemudian melakukan penggantian string tunggal, jadi ini jelas dalam waktu yang konstan. Ini pada dasarnya setara dengan:

$x="#";
eval $x;
$x=~s/#//;

Dua kali lipat:

#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;
#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;

Bit yang sebenarnya membutuhkan waktu eksponensial adalah eval kedua: ia mengevaluasi perintah say for(1..2**$_), yang mendaftar semua angka dari 1 hingga 2 ^ N, yang jelas membutuhkan waktu eksponensial.

Terbalik:

;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#

Ini (secara naif) menghitung penjumlahan dari input, yang jelas membutuhkan waktu linier (karena setiap penambahan adalah dalam waktu konstan). Kode yang benar-benar dijalankan setara dengan:

$x+=$_ for(1..$_);
$_=$x;

Baris terakhir hanya agar ketika perintah ini diulangi akan memakan waktu kuadratik.

Terbalik dan digandakan:

;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#
;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#

Ini sekarang mengambil penjumlahan dari penjumlahan input (dan menambahkannya ke penjumlahan input, tetapi apa pun). Karena memang melakukan N^2penambahan pesanan , ini membutuhkan waktu kuadratik. Ini pada dasarnya setara dengan:

$x=0;
$x+=$_ for(1..$_);
$_=$x;
$x+=$_ for(1..$_);
$_=$x;

Baris kedua menemukan penjumlahan dari input, melakukan Npenambahan, sedangkan yang keempat melakukan summation(N)penambahan, yaitu O(N^2).

Chris
sumber
Bagus! Melakukan itu dalam bahasa umum akan sulit! Ini yang saya dapatkan!
Arjun
Bagus, ini cukup bagus. Anda mungkin bermaksud $x.=q;##say...bukannya $x.=q;#say...(dengan dua #bukannya 1). (Itu akan menjelaskan mengapa Anda menghitung 76 byte, bukan 75). Juga, Anda harus menghitung -nbendera dalam bytecount Anda, karena program Anda tidak akan banyak membantu tanpa itu.
Dada
@Dada Saya tidak sengaja mengubah evaldan s///perintahnya. Jika Anda melakukan yang evalpertama, Anda hanya perlu yang satu #. Tangkapan yang bagus!
Chris
@ Chris Benar, ini memang berhasil. Anda mungkin dapat menghilangkan yang terakhir #: produk yang $x=~s/#//;dibalik ;//#/s~=x$, yang dalam konteks Anda tidak melakukan apa-apa, seperti yang terjadi pada pemimpin #. (Saya belum mengujinya). Apapun, miliki +1!
Dada
@Dada tangkapan bagus sekali lagi!
Chris
17

Sebenarnya , 20 byte

";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"

Cobalah online!

Memasukkan: 5

Keluaran:

rⁿ@╜╖1(;
[0]
5

Terbalik:

";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"

Cobalah online!

Keluaran:

rⁿ╜╖1(;
[0, 1, 2, 3, 4]
5

Dua kali lipat:

";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"

Cobalah online!

Keluaran:

rⁿ@╜╖1(;
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
rⁿ@╜╖1(;
rⁿ@╜╖1(;
[0]

Berganda dan terbalik:

";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"

Cobalah online!

Keluaran:

rⁿ╜╖1(;
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
rⁿ╜╖1(;
rⁿ╜╖1(;
[0, 1, 2, 3, 4]

Ide utama

Sebenarnya adalah bahasa berbasis stack.

  • abcadalah program yang memiliki kompleksitas O (1 n ), dan gandanya memiliki kompleksitas O (2 n ).
  • defadalah program yang memiliki kompleksitas O (n 1 ), dan gandanya memiliki kompleksitas O (n 2 ).

Lalu, kiriman saya adalah "abc"ƒ"fed", di mana ƒdievaluasi. Dengan begitu, "fed"tidak akan dievaluasi.

Generasi program individu

Kodesemu dari komponen pertama ;(1╖╜ⁿr:

register += 1 # register is default 0
print(range(register**input))

Kode pseud dari komponen kedua ;(1╖╜ⁿ@r:

register += 1 # register is default 0
print(range(input**register))
Biarawati Bocor
sumber
Saya tidak pernah berpikir ini akan mungkin! Kerja bagus, tuan! +1
Arjun
@ Arjun Terima kasih atas penghargaan Anda.
Leaky Nun
Ini sangat bagus dan benar-benar naik ke tantangan dengan tidak menggunakan komentar IMO. Luar biasa!
ShreevatsaR
1
Yah ini sebenarnya memiliki komentar ... string tidak dievaluasi dan NOP ...
Leaky Nun
4

Jelly , 20 byte

Sebagian terinspirasi oleh solusi Sebenarnya Leaky Nun .

Baris baru terkemuka dan tertinggal sangat penting.

Normal:


⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

Cobalah online!

Memasukkan: 5

Keluaran: 

610

Terbalik:


⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

Cobalah online!

Memasukkan: 5

Keluaran:

[1, 2, 3, 4, 5]10

Dua kali lipat


⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

Cobalah online!

Memasukkan: 5

Keluaran:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]10

Dua kali lipat dan Terbalik


⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

Cobalah online!

Memasukkan: 5

Keluaran:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]10

Penjelasan

Kuncinya di sini adalah Ŀ, yang berarti "menyebut tautan di indeks n sebagai monad." Tautan diindeks dari atas ke bawah mulai dari 1, tidak termasuk tautan utama (terbawah). Ŀbersifat modular juga, jadi jika Anda mencoba untuk memanggil tautan nomor 7 dari 5 tautan, Anda sebenarnya akan memanggil tautan 2.

Tautan yang dipanggil dalam program ini selalu merupakan yang ada di indeks 10 ( ⁵), apa pun versi programnya. Namun, tautan mana yang berada di indeks 10 tergantung pada versinya.

Yang ⁵muncul setelah masing Ŀ- masing ada sehingga tidak pecah ketika terbalik. Program akan melakukan kesalahan saat parse-time jika tidak ada nomor sebelumnya Ŀ. Memiliki ⁵after adalah nilad yang tidak pada tempatnya, yang langsung menuju ke output.

Versi asli memanggil tautan ‘, yang menghitung n +1.

Versi terbalik memanggil tautan R, yang menghasilkan kisaran 1. n.

Versi ganda memanggil tautan 2*R, yang menghitung 2 n dan menghasilkan kisaran 1 .. 2 n .

Versi ganda dan terbalik memanggil tautan ²R, yang menghitung n 2 dan menghasilkan kisaran 1. .. n 2 .

Kucing Bisnis
sumber
4

Befunge-98 , 50 byte

Normal

\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;

Sejauh ini, ini adalah program paling sederhana dari 4 - satu-satunya perintah yang dieksekusi adalah sebagai berikut:

\+]
  !
  : @
&$< ^&;

Program ini melakukan beberapa hal yang tidak penting sebelum menekan perintah "belok kanan" ( ]) dan panah. Kemudian muncul 2 "take input" perintah. Karena hanya ada 1 angka dalam input dan karena cara TIO memperlakukan &, program keluar setelah 60 detik. Jika ada 2 input (dan karena saya bisa tanpa menambahkan byte), IP akan naik ke fungsi "end program".

Cobalah online!

Terbalik

;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\

Yang ini sedikit lebih rumit. perintah yang relevan adalah sebagai berikut:

;&^  $
  >:*[
;< $#]#; :. 1-:!k@
  :

yang setara dengan

;&^                   Takes input and sends the IP up. the ; is a no-op
  :                   Duplicates the input.
  >:*[                Duplicates and multiplies, so that the stack is [N, N^2
     $                Drops the top of the stack, so that the top is N
     ]#;              Turns right, into the loop
         :.           Prints, because we have space and it's nice to do
            1-        Subtracts 1 from N
              :!k@    If (N=0), end the program. This is repeated until N=0
;< $#]#;              This bit is skipped on a loop because of the ;s, which comment out things

Bagian penting di sini adalah :. 1-:!k@bit. Ini berguna karena selama kita mendorong kompleksitas yang benar ke tumpukan sebelum mengeksekusi dalam kompleksitas waktu yang lebih rendah, kita bisa mendapatkan yang diinginkan. Ini akan digunakan dalam 2 program yang tersisa dengan cara ini.

Cobalah online!

Dua kali lipat

\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;

Dan perintah yang relevan adalah:

\+]
  !
  :
&$< ^&;\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;

Program ini masuk ke dalam 2 loop. Pertama, ia mengikuti jalur yang sama dengan program normal, yang mendorong 1 dan N ke stack, tetapi alih-alih membungkus ke yang kedua &, IP melompati komentar ke dalam loop yang mendorong 2^N:

        vk!:    If N is 0, go to the next loop.
      -1        Subtract 1 from N
 +  :\          Pulls the 1 up to the top of the stack and doubles it
  ]#            A no-op
\               Pulls N-1 to the top again

Bit lain pada baris 4 dilewati menggunakan ;s

Setelah (2 ^ N) didorong ke tumpukan, kami memindahkan garis ke dalam lingkaran pencetakan yang disebutkan di atas. Karena loop pertama, kompleksitas waktu adalah Θ (N + 2 ^ N), tetapi itu berkurang menjadi Θ (2 ^ N).

Cobalah online!

Dua kali lipat dan Terbalik

;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\

Perintah yang relevan:

;&^

;< $#]#; :. 1-:!k@

 @>:*[

  :

Fungsi ini hampir identik dengan program terbalik, tetapi N^2tidak muncul dari tumpukan, karena baris pertama dari salinan kedua program ditambahkan ke baris terakhir yang pertama, yang berarti bahwa perintah drop ( $) tidak pernah dijalankan , jadi kita masuk ke lingkaran pencetakan dengan N^2di bagian atas tumpukan.

Cobalah online!

MildlyMilquetoast
sumber