시간복잡도에 대해 설명해 주세요.

• 시간 복잡도는 알고리즘을 구현할 때, 효율적인 방법을 찾기 위해 고려하는 것으로, "값의 변화에 따라 연산을 수행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는가" 에 대한 개념이다.

• 시간 복잡도는 크게 세 가지로 나눌 수 있다.

  • Big-O(빅-오) : 상하 점근(최악의 경우를 고려)

  • Big-Ω(빅-오메가) : 하한 점근(최선의 경우를 고려)

  • Big-θ(빅-세타) : 그 둘의 평균

• 가장 많이 사용되는 것은 Big-O로 최악의 경우를 고려하므로 프로그램이 실행되는 과정에서 소요되는 최대의 시간을 고려할 수 있다.

• "최소한 특정 시간 이상이 걸린다" 또는 "이 정도 시간이 걸린다"를 고려하는 것보다 "이 정도 시간까지 걸릴 수 있다" 를 고려해야 그에 맞는 대응이 가능하기 때문에 개발을 하는 데에 있어서는 Big-O로 시간 복잡도를 계산한다.

• 시간 복잡도 순서

  • O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)