第二章2.2アルゴリズム時間複雑度例題説明

#%% md

時間の複雑さと空間の複雑さ

これはいかなるAIエンジニアが深く理解しなければならない概念である.各設計アルゴリズムについて,O(N),O(N^2):o notationをこの2つの側面から解析する必要がある.

#%%

int a = 0, b = 0; 

for (i = 0; i < N; i++) { #  O(N)+O(N)=2*O(N)=O(N)
    a = a + rand();# N*1    = O(N)
    b = b + rand();# N*1    = O(N)
} 
for (j = 0; j < N/2; j++) { 
    b = b + rand(); # N/2 *1    = 1/2*O(N)=O(N)
} 

#%% md
時間の複雑さ?空間の複雑さ?O(N)2単位のメモリ容量=O(1)#constant space complexity

#%%

int a = 0; i,j
for (i = 0; i < N; i++) {      
    for (j = N; j > i; j--) { 
        a = a + i + j; 
    } 
} 

i=0: j=N...1   N
i=1: j=N...2   N-1
i=2: j=N...3   N-2
i=N-1: j=N      1
    
total = 1+2+3,...+N = N*(N+1)/2 = N*N/2 + N/2 
= 1/2*O(N^2) + 1/2*O(N) = O(N^2) + O(N) = O(N^2)

#%%

時間複雑度:O(N^2);空間複雑度:O(1)

#%%

int i, j, k = 0; 
for (i = n / 2; i <= n; i++) { 
    for (j = 2; j <= n; j = j * 2) { 
        k = k + n / 2; 
    } 
} 

O(n*log n)

#%%



#%%

int a = 0, i = N; 
while (i > 0) { 
    a += i;  # 1   
    i /= 2;   #1   
} 

N = 40;  i=40

i=20  2
i=10  2
i=5   2
i=2   2
i=1   2
i=0   2
terminate
2*log(N) = 2* O(log N) = O(log N)
 


#%%



#%% md

アルゴリズムXの効率がYより高いと言うたびに?時間複雑度X:o(log n)>Y:o(n)o(n log n)>Y:o(n^2)
X実际の効率(秒来)>Y実际の効率(秒)は必ずしも!!!n十分大きい
#%%
定理:if xの時間複雑度はyの時間複雑度より優れているが,n>Mの場合,Xの実際の効率がYの実際の効率よりも優れていることを保証できる十分な数Mが存在すると仮定する.
C*O(N)=O(N)if only if CはNと相関がない
O(1)O(log n)o(n)o(nlog n):quicksort,heapsort,mergesort o(n^2)o(n^3)...o(2^n)o(3^n)o(log n):element(tree,heapから),binary searchを探す