시간 복잡도란?
시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 말합니다.
보통 알고리즘의 반복문을 보고 성능을 평가하게 됩니다.
한 가지 예를 들어보겠습니다.
[1, 2, 3, 4, 5]위의 배열에서 숫자 3을 찾아야 하는 알고리즘을 만들어야 할 때 간단하게 반복문 안에서 IF문을 사용해 3을 찾을 수 있게 됩니다.
그렇다면 좌측의 1부터 순서대로 3을 찾아낼 때 까지 반복문이 실행될 것이고 3를 찾아내면 반복문은 종료될 것 입니다.
이때, 3이라는 원소가 배열 어느 위치에 있느냐에 따라 문제를 해결할 수 있는 시간이 달라집니다. 그렇기 때문에 경우를 나누어서 성능을 평가하게 됩니다.
Big-Ω: 가장 빠르게 찾을 경우
Big-O: 가장 오래 걸릴 경우
Big-Θ: 평균의 경우
위의 표현 중 Big-O와 Big-Θ를 많이 사용하는데 그 중에서도 Big-O를 가장 많이 사용합니다.
즉, 배열의 길이가 n이라면 가장 오래 걸릴 경우 n번 만에 데이터를 찾게될 수 있습니다. 이를 Big-O 표기법으로 O(n)으로 표현합니다.
건데브