65

Napisz program (lub funkcję), który wykazuje cztery typowe złożone złożoności czasu O w zależności od tego, jak jest uruchamiany. W dowolnej formie przyjmuje dodatnią liczbę całkowitą N, którą możesz założyć, że jest mniejsza niż 2 ³¹ .

Gdy program jest uruchamiany w oryginalnej formie, powinien mieć stałą złożoność. Oznacza to, że złożoność powinna wynosić Θ (1) lub równoważnie Θ (1 ^ N) .
Gdy program zostanie odwrócony i uruchomiony, powinien mieć złożoność liniową . Oznacza to, że złożoność powinna wynosić Θ (N) lub równoważnie Θ (N ^ 1) .
(Ma to sens, ponieważ N^1jest 1^Nodwrócone).
Gdy program zostanie podwojona , czyli łączone do siebie i uruchomić powinien mieć wykładniczą złożoność, a konkretnie 2 ^N . Oznacza to, że złożoność powinna wynosić Θ (2 ^ N) .
(Ma to sens, ponieważ 2in 2^Njest podwójnie 1in 1^N.)
Gdy program zostanie podwojona i odwrócone i uruchomić powinien mieć wielomian złożoności, a konkretnie N ² . Oznacza to, że złożoność powinna wynosić Θ (N ^ 2) .
(Ma to sens, ponieważ N^2jest 2^Nodwrócone).

Te cztery przypadki są jedynymi, z którymi musisz sobie poradzić.

Zauważ, że dla dokładności używam dużej theta (Θ) zamiast dużej O, ponieważ środowiska wykonawcze programów muszą być ograniczone zarówno powyżej, jak i poniżej wymaganymi złożonościami. W przeciwnym razie samo napisanie funkcji w O (1) spełni wszystkie cztery punkty. Nie jest zbyt ważne, aby zrozumieć niuans tutaj. Głównie, jeśli twój program wykonuje operacje k * f (N) dla pewnej stałej k, to prawdopodobnie jest to Θ (f (N)).

Przykład

Jeśli oryginalny program był
ABCDE
następnie uruchomienie powinno zająć cały czas. To znaczy, czy wejście N wynosi 1, czy 2147483647 (2 ³¹ -1), czy jakakolwiek wartość pomiędzy nimi, powinno zakończyć się mniej więcej w tym samym czasie.

Odwrócona wersja programu
EDCBA
powinien zająć czas liniowy w odniesieniu do N. To znaczy, czas potrzebny do zakończenia powinien być w przybliżeniu proporcjonalny do N. Tak więc N = 1 zajmuje najmniej czasu, a N = 2147483647 zajmuje najwięcej.

Podwójna wersja programu
ABCDEABCDE
Należy wziąć dwa-do-N godziny w kategoriach N. Oznacza to, że czas potrzebny do rozwiązania powinny być w przybliżeniu proporcjonalna do 2 ^N . Więc jeśli N = 1 kończy się w ciągu około sekundy, N = 60 zajęłoby więcej niż wiek wszechświata, aby zakończyć. (Nie, nie musisz tego testować.)

Podwojona i odwrócona wersja programu
EDCBAEDCBA
powinien zająć do kwadratu czas w kategoriach N. Oznacza to, że czas potrzebny do zakończenia powinien być w przybliżeniu proporcjonalny do N * N. Więc jeśli N = 1 zakończy się za około sekundę, N = 60 zajmie około godziny.

Detale

Musisz pokazać lub argumentować, że twoje programy działają w złożoności, o której mówisz, że są. Podanie pewnych danych dotyczących czasu jest dobrym pomysłem, ale spróbuj także wyjaśnić, dlaczego teoretycznie złożoność jest poprawna.
Jest w porządku, jeśli w praktyce czasy, w których twoje programy nie są w pełni reprezentatywne dla ich złożoności (a nawet determinizmu). np. wejście N + 1 może czasami działać szybciej niż N.
Środowisko, w którym uruchamiasz swoje programy, ma znaczenie. Możesz przyjąć podstawowe założenia dotyczące tego, że popularne języki nigdy celowo nie marnują czasu na algorytmy, ale na przykład, jeśli wiesz, że twoja konkretna wersja Java implementuje sortowanie bąbelkowe zamiast szybszego algorytmu sortowania , powinieneś wziąć to pod uwagę, jeśli wykonujesz jakiekolwiek sortowanie .
Dla wszystkich zawiłości tutaj załóżmy, że mówimy o scenariuszach najgorszych przypadków , a nie najlepszych lub średnich.
Złożoność przestrzenna programów nie ma znaczenia, tylko złożoność czasowa.
Programy mogą wysyłać cokolwiek. Liczy się tylko to, że przyjmują dodatnią liczbę całkowitą N i mają prawidłową złożoność czasową.
Komentarze i programy wieloliniowe są dozwolone. (Możesz założyć, że \r\nodwrócona jest \r\nzgodna z Windows).

Wielkie przypomnienia

Od najszybszego do najwolniejszego O(1), O(N), O(N^2), O(2^N)(kolejność 1, 2, 4, 3 powyżej).

Wolniejsze terminy zawsze dominują, np O(2^N + N^2 + N) = O(2^N).

O(k*f(N)) = O(f(N))dla stałej k. Więc O(2) = O(30) = O(1)i O(2*N) = O(0.1*N) = O(N).

Pamiętaj O(N^2) != O(N^3)i O(2^N) != O(3^N).

Zgrabny duży ściągawka O.

Punktacja

To normalny kod golfowy. Najkrótszy oryginalny program (czas stały) w bajtach wygrywa.

code-golf integer source-layout restricted-complexity set-theory Hobby Calvina
źródło

Doskonałe pytanie! Drobny punkt: nie musimy określać najgorszego / najlepszego przypadku / średniego przypadku, ponieważ jedynym wejściem, który liczy się jako rozmiar N, jest sama liczba N (która BTW nie jest zwykłym pojęciem wielkości wejściowej: traktuj wejście N jako logarytmu wielkości N). Zatem dla każdego N jest tylko jeden przypadek, który jest jednocześnie najlepszym, najgorszym i przeciętnym przypadkiem.

ShreevatsaR

5

Wygląda na to, że odstąpiłeś od zwykłych definicji złożoności. Zawsze definiujemy złożoność czasową algorytmu w zależności od wielkości jego danych wejściowych . W przypadku, gdy dane wejściowe są liczbą, wielkość danych wejściowych jest logarytmem podstawowym 2 tej liczby. Tak więc program n = input(); for i in xrange(n): passma wykładniczą złożoność, ponieważ wykonuje 2 ** kkroki, gdzie k = log_2(n)jest wielkość wejściowa. Należy wyjaśnić, czy tak jest, ponieważ radykalnie zmienia to wymagania.

wchargin

36

Python 3 , 102 bajty

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

Programowanie mocy: O (1 ^ N), O (N ^ 1), O (2 ^ N), O (N ^ 2) wszystko w jednym

Przykład

Detale

Wielkie przypomnienia

Punktacja

Odpowiedzi:

Python 3 , 102 bajty

Perl 5, 82 73 71 + 1 (dla flagi -n) = 72 bajty

Właściwie 20 bajtów

Główny pomysł

Generowanie indywidualnego programu

Galaretka , 20 bajtów

Normalna:

Wywrócony:

Podwojony

Podwojone i cofnięte

Wyjaśnienie

Befunge-98 , 50 bajtów

Normalna

Wywrócony

Podwojony

Podwojone i cofnięte