Uproszczenie złożoności Big-O tego wykładniczego algorytmu

Question

Mam algorytm liczenia, dla którego próbuję uzyskać ogólny opis big-o. Jest straszliwie zagnieżdżony i strasznie wykładniczy. Oto ona:

1. For each T_i in T 
2. For k = 1 to max_k 
3. For each of 2^k*(n choose k) items 
4. For each t in T_i 
5. check if the item is in t...etc. 

Oto pomysł linia po linii z każdym systemem

1. Jest to prosty podział i mam zamiar po prostu dać mu stałą c1.
2. max_k to mała liczba, zawsze mniejsza niż n, może około 4 lub 5. Będę używał k poniżej.
3. Pętla ta zawsze prowadzi 2^k * (n wybrać k) razy
4. Rozważając linia 1 Stałe możemy uogólnić tę linię i wiem, że nigdy nie będzie strzelać więcej niż 2^n razy w sumie w najgorszym przypadku, ale generalnie będzie działał ułamek 2^n razy, więc nazwiemy to (2^n)/c2
5. Jest to prosta operacja if-instrukcja wewnątrz wszystkich tych pętli, więc c3.

Mnożąc to wszystko razem daje:

c1 * k * 2^k * (n choose k) * (2^n)/c2 * c3 

Ponieważ chcę reprezentację big-O, ignorując stałe daje:

k * 2^k * (n choose k) * (2^n) 

Wiadomo, że (n wybrać k) jest ograniczona powyżej (n * e/K)^k, tak:

O(k * 2^k * (n * e/k)^k * (2^n)) 

My questi on jest, co mogę tu zignorować ... 2^n jest z pewnością dominującym terminem, ponieważ n jest zawsze większe niż k, a zazwyczaj o wiele bardziej. Czy można to uprościć do O (2^n)? Lub O (2^straszne)? Czy powinienem zostawić w 2^k, jak w O (2^k * 2^n)? (lub pozostawić wszystkie warunki?)

Rozumiem, że jeśli k lub max_k może konkurować lub przewyższać n, to są one niezbędne. Ale skoro są one zawsze zdominowane, czy można je odrzucić, podobnie jak terminy wielomianowe rzędu niższego rzędu? Przypuszczam, że cały bałagan czasu wykładniczego mnie myli. Wszelkie porady są mile widziane.

Answer 1

Moje zrozumienie jest, że jeśli k lub max_k może konkurować lub przekroczą N, to są one niezbędne

To prawda, ale na odwrót nie jest - co oznacza - nie mogą być ignorowane, gdy dochodzi do dużej notacji O, nawet jeśli nie konkuruje z n. Można go zignorować tylko wtedy, gdy max_k jest ograniczone przez stałą (jest stała c taka, że ​​k <= c). Na przykład - algorytmy O(n * logk) nie są , ponieważ współczynnik k nie jest ograniczony, a zatem istnieje k taki, że nlogk > c*n dla każdej stałej c.

Ponieważ wyrażenie, które otrzymałeś, jest produktem, możesz zignorować tylko stałe, które w twoim przypadku - tylko e dostaniesz O(k*2^k * (n/k)^k * 2^n).

Jeśli k jest ograniczony, można usunąć go z ekspresją oraz w asymptotyczne tempo wzrostu, a dostaniesz O(n^k* 2^n).Zauważ, że nawet w tym przypadku, chociaż n^k << 2^n, nadal nie można go zignorować, ponieważ dla każdej stałej c istnieje pewna liczba n taka, że ​​c*2^n < n^k *2^n, więc algorytm nie jest liczbą O(2^n).

Mniejsze czynniki można zignorować, jeśli chodzi o dodawanie. Jeśli k < n to O(n + k) = O(n), ponieważ istnieją stałe c,N takie, że dla wszystkich n > N: c*n < n + k, ale to oczywiście nie jest prawdą, gdy mamy do czynienia z produktem.