시간 복잡도에 대하여

---

알고리즘 분석의 2가지 측면

• 알고리즘 수행 시간 분석 : 시간 복잡도
• 알고리즘이 사용하는 기억 공간 분석 : 공간 복잡도

---

시간 복잡도

동일한 조건에서, 똑같은 일을 하는데 알고리즘 A가 30개의 연산을 수행하였고, 알고리즘 B가 300개의 연산을 수행하였다면, 알고리즘 B가 알고리즘 A보다 수행하는 연산의 수가 더 많다.
따라서 알고리즘 A가 효율적인 알고리즘이라고 할 수 있는데, 이것이 시간 복잡도의 기본 개념이다.
연산들의 수행 횟수는 프로그램에서 주어지는 입력의 개수 n에 따라 변하게 된다. 따라서 일반적으로 연산의 수행횟수는 고정된 숫자가 아니라 n에 대한 함수가 된다.
연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간 복잡도 함수라고 하고 T(n)으로 표기한다.

알고리즘 A

• 연산을 기준으로 대입 연산 1회, 나눗셈 연산 1회 => 총 2회

sum <- n * n;

알고리즘 B

• 연산을 기준으로 대입 연산 n회, 덧셈 연산 n회 => 총 2n회

for i <- 1 to n do  
  sum <- sum + n;

알고리즘 C

• 연산을 기준으로 대입 연산 nn, 덧셈 연산 nn => 2n^2 회

for i <- 1 to n do 
  for j <- 1 to n do 
    sum <- sum + 1;