ㅇㅏㄹ고리즘을은 문제에 대한 해답을 찾는 것이 중요하다.
그러나 그에 못지 않게 효율적인 방법으로 고민하는것도 중요하다.
효율적인 방법 고민 = 시간 복잡도를 고민한다.

시간 복잡도

입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘. 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다.

Big-O 표기법

시간 복잡도를 표기하는 방법은 다음과 같다.
Big-O(빅-오)
Big-Ω(빅-오메가)
Big-θ(빅-세타)

위 세가지 표기법은 시간 복잡도를 최악,최선,중간(평균) 의 경우에 대하여 나타낸다. 이 중에서 Big-O표기법이 가장 자주 사용된다. Big-O표기법은 최악 을 고려하므로 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문에 많이 사용된다. 예를 들어 결과를 반환하는데 최선의 경우 1초, 평균적으로 1분, 최악의 경우 1시간이 걸리는 알고리즘을 구현했고 최선의 경우를 고려한다고 가정했다. 이 알고리즘을 100번실행을 한다면 100초가 걸린다. 만약 실제로 걸린 시간이 1시간이 훌쩍 넘겼다면 "어디서 문제가 생긴거지?"하는 의문이 생긴다. 최선만의 경우만 고려했으니 어디서 문제가 생겼는지 발생하는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하므로 문제를 파악하는데 시간이 많이 걸린다. 평균도 마찬가지이다.
위와 같이 최악의 경우가 발생하지 않기를 바라며 시간을 계산하는것보다
👉 최악의 경우도 고려해 대비 하는것이 바람직하다 따라서 다른 표기법보다 Big-O표기법을 많이 사용한다.

Big-O(빅-오): 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?