이 특정 비용 함수에 대한 큰 오 표기법

Question

질문 : 더 많은 공간이 필요한 경우 배열의 크기를 두 배로 늘리는 스택 비용을 나타내는 큰 오 표기법은 무엇입니까? 더 크지 만 더 작지는 않습니다.

예 :

N = [size] 
1 = [x] 
2 = [x,x] 
3 = [x,x,x,x] 
4 = [x,x,x,x] 
5 = [x,x,x,x,x,x,x,x] 
6 = [x,x,x,x,x,x,x,x] 
7 = [x,x,x,x,x,x,x,x] 
8 = [x,x,x,x,x,x,x,x] 
9 = [x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x] 
10 =[x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x] 

내가 같이있어 : lim as n -> infinity of log_2(n) = infinity 때문에, 내가 O(2^N)로 해석 (2^(log_2(n))) + 1

에 해당

T(N) = Summation from i = 0, to log_2(N) of (2^i) 

. (2^(log_2(n))) + 1

Answer 1

내가 힘든 시간 코드의 분석을 파악하는 데 문제 : 그래서 본질적으로

는 ... 이것에 대한 큰 아 것입니다. 오히려 다음과 같은 분석을 통해 실행 시간이 실제로 O (N)가 될 것이라고 확신 할 수 있습니다.

N 요소를 저장하는 경우 2, 4, 8, 16, 32, 64, ..... (2) X =^N.

따라서, 각각 X = N log_2

동작을 배열 크기와 동일한 크기를 선정을 2^X 요소가 발생된다. 따라서 전체 크기 조정 오버 헤드가 표현 될 수 등 :

cost = 2^0 + 2^1 + 2^2 + 2^3 ......2^x 
    = (2^x-1)/(2-1)  
    = 2^x - 1 
    = 2^(log_2 N) - 1 
    = N^(log_2 2)-1 
    = N-1 
    = O(N)