potrzebne do uzyskania złożoność Big-O tego wyrażenia:Big-O złożoność c^n + n * (logn)^2 + (10 * N)^c
c^n + n * (log (n))^2 + (10 * n)^c
gdzie c jest stałą, a n jest zmienną.
Jestem prawie pewien, że rozumiem, jak wyprowadzić złożoność Big-O każdego pojedynczego punktu osobno, po prostu nie wiem, jak zmienia się złożoność Big-O, gdy terminy są połączone w ten sposób.
Pomysły?
Każda pomoc będzie świetna, dzięki.
Notacja O() uważa najwyższy termin; pomyśl o tym, który będzie dominował dla bardzo, bardzo dużych wartości n.
W twoim przypadku najwyższy termin to c^n; pozostałe są zasadniczo wielomianami. Jest to wykładnicza złożoność.
W typowym zastosowaniu, formalna określenie zapisu o Nie stosuje się bezpośrednio; a oznaczenie wyjścia dla funkcji f (x) jest uzyskane przez następujące zasady uproszczenia:
- Jeśli f (x) stanowi sumę różnych warunkach, jeden z największą szybkość wzrostu jest utrzymywana i wszystkich inne zostały pominięte.
- Jeśli f (x) jest iloczynem kilku czynników, wszelkie stałe (warunki w produkcie, które nie zależą od x) są pomijane.
Myślałem, że Google jest :) – akif
Odpowiedź zależy od | c |
Jeśli | c | < = 1 to O (n * (log (n))^2)
IF | c | > 1 to O (c^n)
+1 Yay za odpowiedź, która przechwytuje oba przypadki wartości C. :-P –
Nigdy nie myślałem o tym wcześniej, ale tutaj idzie. Jeśli złożoność zależy od wielkości C, czy oznacza to, że zależy to również od jednostek użytych do pomiaru C? Jeśli nie, to w jakich jednostkach należy mierzyć C? – Stewart
@Stewart Nie sądzę, że c można wyrazić w niektórych jednostkach. Gdyby mógł, to jednostka wyrażenia zależałaby od n i (10 * n)^c nie miałaby sensu. –
+1 - Tak, to prawda. Usunąłem swoją odpowiedź. Z jakiegoś powodu odczytałem go jako n^c. –
Jedno bardzo ważne założenie: C musi być większe niż 1. :-P –