알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 라는 말이다.
효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기이다.
우리는 프로그램의 성능을 정확하게 알 수 있을까?
일단 프로그램의 정확한 성능을 측정하기 위해서는 고려해야할것들이 아주 많다.
ex) 입력 크기, 하드웨어 성능, 운영체제 성능, 컴퍼일러 최적화, 비동기 로직 등등…
만약 항상 같은 데이터를 쓰고 같은 하드웨어 같은 성능측정 프로그램을 써도 항상 같은 결과가 나오진 않는다.
실행환경과 메모리 사용량에 따라 다른 결과가 나오기 때문이다.
따라서 프로그램의 성능을 정확히 파악하는 것은 불가능하다고 볼 수 있다.
그렇기 때문에 컴퓨터 과학자들은 대략적인 성능을 비교하기 위한 상대적인 표기법을 사용하기러 하였다.
그것이 바로 Big-O notation(빅오 표기법) 이다.
Big-O 표기법은 시간 복잡도를 나타내기 위한 방법 중 하나이다.
상수 시간 < 로그 시간 < 선형 시간 < 선형 로그 시간 < 2차 시간 < 지수 시간 < 팩토리얼 시간
이라고 부른다.
참고로 로그의 밑은 2 이다.