[알고리즘] 복잡도 분석

< 알고리즘 복잡도 분석 >

Complexity Analysis

• 특정 입력값에 대한 연산 수
• 연산의 기준: 기본 연산(operation)의 수를 세기

점근적 표기법(Asymptotic Notation)

• 단순하게 기본 연산의 수를 세기

최악의 경우 분석(Worst-case Analysis)

• 모든 경우를 고려하기 위해 최악의 경우를 따짐
• 평균적 경우(Average Case), 최선의 경우(Best Case)도 고려 가능
• 최악의 경우 분석을 위해 상수는 무시
• 반복의 횟수도 분석: 연산의 시간은 상수

for (i = 1; i <= n; i++)
    // 단순 연산 O(1)
    // 총 n번 수행 O(n)