1. 알고리즘 - 시간복잡도

1. 시간복잡도?

• 시간복잡도는 알고리즘의 성능을 분석되는데 사용되는 방법
• 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도
• 절대적인 수행 시간은 컴퓨터마다 다르다.

1.1 입력(Input)값의 예시

• 배열(array) -> 배열의 크기(size of array)
• 그래프(graph) -> 정점과 간선의 개수

1.2 시간복잡도의 종류

1. Every-Case Time Complexity ( 𝑇(𝑛) )

입력 크기 n 이 입력됐을 때, 알고리즘이 연산을 수행하는 횟수

• 입력 크기에만 종속되며, 어떤 입력값이 들어오더라도 일정하다.

2. The Worst Case Time Complexity( 𝑊(𝑛) )

입력크기 n 이 주어졌을 때, 알고리즘이 연산을 수행하는 최대 횟수

• 입력크기와 입력값 모두에 종속되며, 단위연산이 수행되는 횟수가 최대인 경우 선택

3. The Best Case Time Complexity ( 𝐵(𝑛) )

입력크기 n 이 주어졌을 때, 알고리즘이 연산을 수행하는 최소 횟수

• 입력크기와 입력값 모두에 종속되며, 단위연산이 수행되는 횟수가 최소인 경우 선택

4. The Average Case Time Complexity ( 𝐴(𝑛) )

입력크기 n 이 주어졌을 때, 알고리즘이 연산을 수행하는 평균 횟수

• 입력크기와 입력값 모두에 종속되며, 모든 입력에 대해서 단위연산이 수행되는 기대치
  • 함수의 연산이 두 실수의 덧셈 이라면, 배열의 크기에만 수행 시간이 영향을 받으므로 𝑇(𝑛) = 𝑛 
  • 즉 입력 크기에만 종속되는 Every-Case Time Complexity로 분석할 수 있다.
  • 𝑇(𝑛)으로 분석할 수 있다면 다른 복잡도도 𝑊(𝑛) = 𝐴(𝑛) = 𝐵(𝑛) = 𝑇(𝑛) 동일해진다.

5. Big-Oh ( O(𝑛) ) 표기법 

• 정의

𝑔(𝑛) = 𝑂(𝑓(𝑛)) (read as "𝑔 of 𝑛 is big oh of 𝑓 of 𝑛") iff there exist positive constants 𝑐 and 𝑛0 such that 𝑔(𝑛)≤ 𝑐𝑓(𝑛) for all 𝑛, 𝑛 ≥ 𝑛0.
𝑛 ≥ 𝑛0인 모든 𝑛에 대해 𝑔 𝑛 ≤ 𝑐𝑓(𝑛)인 양의 상수 𝑐와 𝑛0가 존재하면 𝑔(𝑛) = 𝑂(𝑓(𝑛)) 이다.

• 간단히 하면 점근적 상한을 의미한다는 뜻
• g(n)의 성능은 f(n)보다 같거나 좋은 시간 복잡도를 갖는다는 의미

6. Ω(Omega) 표기법

• 정의

𝑔(𝑛) = Ω(𝑓(𝑛)) (read as "𝑔 of 𝑛 is omega of 𝑓 of 𝑛") iff there exist positive constants 𝑐 and 𝑛0 such that 𝑔(𝑛) ≥ 𝑐𝑓(𝑛) for all 𝑛, 𝑛 ≥ 𝑛0
𝑛 ≥ 𝑛0인 모든 𝑛에 대해 𝑔(𝑛) ≥ 𝑐𝑓(𝑛)인 양의 상수 𝑐와 𝑛0가 존재하면 𝑔(𝑛) = Ω(𝑓(𝑛)) 이다.

• Big-oh와 반대로 점근적 하한을 의미
• g(n)의 성능은 f(n)보다 같거나 나쁜 시간복잡도를 갖는다는 의미
• 𝑓(𝑛) = 𝑂(𝑔(𝑛)) 이면, 𝑔(𝑛) = Ω(𝑓(𝑛))

7. Θ(theta) 표기법

𝑔(𝑛) = Θ(𝑓(𝑛)) (read as "𝑔 of 𝑛 is theta of 𝑓 of 𝑛") iff there exist positive constants 𝑐1, 𝑐2 and 𝑛0 such that 𝑐1𝑓(𝑛) ≤ 𝑔(𝑛) ≤ 𝑐2𝑓(𝑛) for all 𝑛, 𝑛 ≥ 𝑛0.
𝑛 ≥ 𝑛0인 모든 𝑛에 대해 𝑐1𝑓(𝑛) ≤ 𝑔(𝑛) ≤ 𝑐2𝑓(𝑛) 인 양의 상수 𝑐1, c2와 𝑛0가 존재하면 𝑔(𝑛) = Θ(𝑓(𝑛)) 이다.

• g(n)이 c1f(n)과 c2f(n)의 사이에 존재합니다.
• 𝑔(𝑛) = Ω(𝑓(𝑛)) 과 𝑔(𝑛) = 𝑂(𝑓(𝑛))을 모두 만족할 수 있음

2. Big-Oh 시간복잡도 순서

𝑂(1) < 𝑂(log n) < 𝑂(n) < 𝑂(nlog n) < 𝑂(n^2) < 𝑂(n^3) < 𝑂(2^n) < 𝑂(n!)

3. 알아두면 유익한! 시간복잡도 특징들

1. g(n) = O(f(n)) 이면 f(n) = Ω(g(n)) 이다.
2. g(n) = Θ(f(n)) 이면 f(n) = Θ(g(n)) 이다.
3. 1 보다 큰 두 수 a,b에 대해, log_a b = Θ(log_b a)