Czas wielomianowy i czas wykładniczy

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?

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.

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 ² ) - czas kwadratowy
• O ( n ^c ) - czas wielomianowy
• O ( c ⁿ ) - 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/

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.

Czas wielomianowy.

Wielomian to suma terminów, które wyglądają jak Constant * x^k Wykładniczy oznacza coś podobnegoConstant * k^x

(w obu przypadkach k jest stałą, a x jest zmienną).

Czas wykonywania algorytmów wykładniczych rośnie znacznie szybciej niż algorytmów wielomianowych.

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

czas wielomianu O (n) ^ k oznacza, że ​​liczba operacji jest proporcjonalna do potęgi k wielkości wejścia

czas wykładniczy O (k) ^ n oznacza, że ​​liczba operacji jest proporcjonalna do wykładnika rozmiaru danych wejściowych

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.