(Data_Structure) 기초 : Pseudocode & Big-Oh

Algorithms을 분석 할 때 아래의 내용들을 고려해야한다.

- Space 사용량

- Running Time

 

 Pseudocode의 예시로 max값을 찾는 code를 보면

Algorithm arrayMax(A[], n)
 Input array A of n integers
 Output Max element of A
 
 currentMax <- A[0]
 for i<-1 to n-1 do
  if A[i]>currentMax then
    currentMax <- A[i]
 return currentMax

이러한 Pseudocode가 있다고 하자

 

이때 n개의 값들이 저장된 A array가 있으니 공간은 n만큼 필요하게 된다.

 

running time을 따지면 for 문에서 A[i]와 currentMax를 비교하게 되는데

for문을 돌릴 때 필요한 i 계산 연산 2n

 for문에서 A[i]와 currentMax를 비교하는 2(n-1)번의 비교가 발생된다.

최악의 경우 currentMax에 A[i]를 입력하니 이것 또한 2(n-1)이 된다.

 

전체적으로 6n-4에 currentMax에 A[0]을 입력하는데 2번의 연산(A[0]에서 한번 입력하는데 1번)

return 출력하는데 1번

 

총 6n-1 만큼의 연산이 생기고 그만큼의 시간이 걸린다.

 

이러한 값을 표현할 때 Big-Oh로 표현한다.