[강의정리] 알고리즘 W2

---

Introduction to Algorithm

알고리즘의 학습목표

Design(설계)

알고리즘 설계하는 기법

Analysis(분석)

• 알고리즘을 분석, 시간/공간 복잡도 구하기

Computational Complexity(계산복잡도)

• 문제를 분석하여 계산적 복잡도 구하기

알고리즘의 분석

시간복잡도(Time Complexity) 분석

• 입력 크기에 따라서 단위연산이 몇번 수행되는지 결정하는 절차(n)

표현 척도

입력크기(input size)

• 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리에서 마디와 이음선의 수, 그래프에서는 정점과 간선의 수

  단위연산(basic operation)

• 비교(comparison), 지정(assignment) 등 시간복잡도에 가장 크게 영향을 미치는 연산

분석 방법의 종류

• 모든경우 분석(Every-case analysis)
• 최악의 경우 분석(Worst-case analysis)
• 평균의 경우 분석(Average-case analysis)
• 최선의 경우 분석(Best-case analysis)

계산복잡도

Big O 표기법

정의 : 점근적 상한(Asymptotic Upper Bound)

차수의 주요 성질

복잡도 함수 순서

• lgn, n, nlgn, n², n^j, n^k, aⁿ, bnⁿ, n!
  k > j > 2, b > a > 1