시간복잡도 기초

[알고리즘의 성능분석]

실행 시간을 측정하는 방법

• 두 개의 알고리즘의 실제 실행 시간을 측정하는 것
• 실제로 구현하는 것이 필요
• 동일한 하드웨어를 사용하여야 함
• clock 함수를 사용 : clock_t clock(void)

알고리즘의 복잡도를 분석하는 방법

• 직접 실행하지 않고서도 수행 시간을 분석하는 것
• 알고리즘이 수행하는 연산의 횟수를 측정하여 비교
• 동일한 기능을 수행할 때, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘

 

• 공간 복잡도 분석 : 수행 시 필요로 하는 메모리 공간 분석
• 시간 복잡도 분석 : 수행 시간 분석 (수행 시간이란 최악의 경우의 입력에 대한 기본 연산 (산술, 대입, 비교, 이동의 횟수))

 

알고리즘 A = 2회

알고리즘 B = n + 1회

알고리즘 C = n^2 + 1회

 

 

[빅오 표기법]

• 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있음
• 가장 빠르게 증가하는 항만을 고려하는 표기법
• 함수의 상항만을 나타내게 됨
• 예시 ) 

 

[빅오 표기법 예시들]

O(n^2)

 

 

O(2/n)

 

[요구 사항에 따라 적절한 알고리즘 설계하기]

• 문제에서 가장 먼저 확인해야 하는 내용은 시간제한 (수행시간 요구사항)

시간 제한이 1초인 문제를 만났을 때, 일반적인 기준

- N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계

-                 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계

-             100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계

-        10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계