C++[7일차](시간 복잡도)

알고리즘의 성능분석

1. 실행 시간을 측정하는 방법
-두 개의 알고리즘의 실제 실행 시간을 측정하는 것
-실제로 구현하는 것이 필요
-동일한 하드웨어를 사용하여야 함

(clock함수 사용: 호출 되었을 때의 시스템 시각 반환)

 

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

-직접 실행하지 않고서도 수행 시간을 분석하는 것
-알고리즘이 수행하는 연산의 횟수를 측정하여 비교
-동일한 기능을 수행할 때, 일반적으로 복잡도가 낮을수록 좋은 알고리즘
-공간 복잡도 분석 : 수행 시 필요로 하는 메모리 공간 분석
-시간 복잡도 분석 : 수행 시간 분석
-수행 시간 : 최악의 경우의 입력에 대한 기본 연산(산술, 대입, 비교, 이동)
의 횟수

 

n을 n번 더하는 문제

 

빅오 표기법

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

예: n=1일때 : T(n) = 1 + 1 + 1 = 3 (33.3%)
     n=10일때 : T(n) = 100 + 10 + 1 = 111 (90%)
     n=100일때 : T(n) = 10000 + 100 + 1 = 10101 (99%)
     n=1,000일때 : T(n) = 1000000 + 1000 + 1 = 1001001 (99.9%)

 

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

1. 문제에서 가장 먼저 확인해야 하는 내용은 시간제한

2. 시간제한이 1초인 문제를 만났을 때, 일반적인 기준
-N의 범위가 500인 경우: 시간 복잡도가 O(N3)인 알고리즘을 설계
-N의 범위가 2,000인 경우: 시간 복잡도가 O(N2)인 알고리즘을 설계
-N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN) 인 알고리즘을 설계
-N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계