진행자

강희주

시간 복잡도(Time Complexity)

1 부터 N까지의 합을 구하는 코드

int sum = 0;
for(int i=1; i<=N; i++)
    sum += i;
-----------------------------------------
int sum = (N+1)*N/2;

• 문제를 해결하기 위한 알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것
  • 알고리즘을 풀 때는 문제에 대한 해답을 찾는 것이 가장 중요
  • 하지만, 그에 못지않게 효율적인 방법으로 문제를 해결했는지도 중요하다.
  • 효율적인 방법을 고민한다는 것 → 시간 복잡도를 고민한다는 것

알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 ’입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’라는 말이다.

효율적인 알고리즘을 구현했다는 것 → 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화했다!

Big-O 표기법

시간 복잡도를 표기하는 방법 중 가장 자주 사용되는 표기법

→ 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다.

📌 최악의 경우까지 고려해야 하는 이유?

만약 알고리즘의 수행시간이 평균적으로 2분이 걸린다고 판단했는데, 만약 실제로 걸린 시간이 1시간이 훌쩍 넘었다면?

→ 평균적인 경우만 고려했으니, 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 한다.