Czy ktoś mógłby wyjaśnić różnicę między algorytmami czasu wielomianowego, czasu nie wielomianowego i czasu wykładniczego?
Na przykład, jeśli algorytm zajmuje O (n ^ 2) czasu, to w której kategorii się znajduje?
Czas wielomianowy i czas wykładniczy
Odpowiedzi:
Spójrz na to .
Wykładniczy jest gorszy niż wielomian.
O (n ^ 2) należy do kategorii kwadratowej, która jest rodzajem wielomianu (szczególny przypadek, w którym wykładnik jest równy 2) i jest lepszy niż wykładniczy.
Wykładniczy jest znacznie gorszy niż wielomian. Zobacz, jak rosną funkcje
n = 10 | 100 | 1000
n^2 = 100 | 10000 | 1000000
k^n = k^10 | k^100 | k^1000
k ^ 1000 jest wyjątkowo duże, chyba że k jest mniejsze niż coś takiego jak 1,1. Na przykład każda cząsteczka we wszechświecie musiałaby wykonać 100 miliardów miliardów operacji na sekundę przez biliony miliardów miliardów lat, aby to osiągnąć.
Nie obliczyłem tego, ale JEST TAK DUŻY.
29
Podobały mi się wszystkie twoje urazy
—
Josephine
k ^ 1000 jest wyjątkowo duże, jeśli k jest znacznie większe niż 1. Jeśli k = 1, to mniej imponujące, a jeśli k = 1.00069387 ..., to 2.
—
Josephine
Co powiesz na n! vs k ^ n. Wiem dla 2 ^ n (najczęściej), n! będzie droższy, ale wierzę, że dla ogólnego k ^ n, gdzie k> 2, n! będzie tańszy.
—
Saad
Cieszę się, że nie powiedziałeś „miliardy i miliardy”. :-)
—
Tom Russell
@Saad n! zawsze będzie droższe niż k ^ n dla stałej k, asymptotycznie. Masz jednak rację, że dzieje się tak tylko wtedy, gdy osiągniemy wysoką wartość n. Przez Wzór Stirlinga, silnia czas powinna zdrożeć wokół gdy n = e * k, gdzie e = 2,71828 ..
—
inavda
Poniżej znajduje się kilka typowych funkcji Big-O podczas analizy algorytmów.
- O ( 1 ) - stały czas
- O ( log (n) ) - czas logarytmiczny
- O ( (log (n)) c ) - czas polilogarytmiczny
- O ( n ) - czas liniowy
- O ( n 2 ) - czas kwadratowy
- O ( n c ) - czas wielomianowy
- O ( c n ) - czas wykładniczy
- O ( n! ) - silnia czasu
(n = wielkość wejścia, c = jakaś stała)
Oto wykres modelu przedstawiający złożoność Big-O niektórych funkcji
Twoje zdrowie :-)
wykres kredytów http://bigocheatsheet.com/
Plus jeden za mniej słów i większą przejrzystość.
—
user3144836
1 = n ^ 0, więc także wielomian
—
BigChief
O (n ^ 2) to czas wielomianowy. Wielomian to f (n) = n ^ 2. Z drugiej strony, O (2 ^ n) to czas wykładniczy, gdzie implikowana funkcja wykładnicza to f (n) = 2 ^ n. Różnica polega na tym, czy funkcja n umieszcza n w podstawie potęgi, czy w samym wykładniku.
Każda wykładnicza funkcja wzrostu będzie rosła znacznie szybciej (długoterminowo) niż jakakolwiek funkcja wielomianu, więc rozróżnienie jest istotne dla wydajności algorytmu, szczególnie w przypadku dużych wartości n.
Ta odpowiedź ma autorytatywny (dobry) charakter, ale wydaje mi się, że różni się ona od odpowiedzi @ dheeran tym, czy podstawa w wykładniczym przypadku jest koniecznie 2. Albo prawdopodobnie źle zrozumiałem i po prostu muszę odkurzyć swoją algebrę.
—
Tom Russell
Wykładnicza (masz funkcję wykładniczą, jeśli MINIMALNA JEDNA WZROST jest zależna od parametru):
- Np. F (x) = stała ^ x
Wielomian (masz funkcję wielomianową, jeśli NIE WYRAŻONY jest zależny od niektórych parametrów funkcji):
- Np. F (x) = x ^ stała
Nie podoba mi się, jeśli po edycji przez użytkownika nic z mojej oryginalnej odpowiedzi nie pozostaje. Czy to coś w rodzaju „łowienia ryb”?
—
Erhard Dinhobl
Muszę się zgodzić. Zmiany są śmieszne.
—
satya na szynach
o (n sequre) jest polinimalną złożonością czasu, podczas gdy o (2 ^ n) jest wykładniczą złożonością czasową, jeśli p = np w najlepszym przypadku, w najgorszym przypadku p = np nie równe, ponieważ rozmiar wejściowy n rośnie tak długo lub rozmiar wejściowy rośnie, więc dłużej będzie to najgorszy przypadek i obsługa tak złożoność rośnie tempo wzrostu i zależy od n wielkość wkładu, gdy wkład jest mały, jest polinimalny, gdy wielkość wkładu jest duży i duży, więc p = np nie jest równy oznacza to, że tempo wzrostu zależy od wielkości wkładu "N ”. optymalizacja, sat, klika i zbiór niezależny również spotykały się wykładniczo do polinimalnych.