시간 복잡도, 점근 표기법(빅오표기법)

자료구조, 알고리즘에서 먼저 익히게 될 개념이 시간 복잡도 일 것이다. 시간 복잡도(Time Complexity)란?

알고리즘이 어떤 문제를 해결하는 데 걸리는 시간 알고리즘의 주요 연산의 횟수를 측정 입력의 크기 n의 함수로 나타냄 예) T(n)= n^2+n 좋은 프로그램인지를 판단하려면 어느 정도 객관적인 지표가 필요하다. 실행 시간으로 판단을 하기엔 {컴파일러, OS, 하드웨어} 등등 결과에 영향을 끼치는 요소가 넘나 많았다.

이때 쓰이는 것 중 하나가 시간 복잡도(Time Complexity)란 것이다. ※시간 복잡도와 비슷한 개념인 공간 복잡도(Space Complexity)가 존재한다.

프로그램이 메모리의 공간을 얼마나 차지하는지를 나타낸다. 버블 정렬(Bubble Sort)를 통해 과정을 알아보자 내부 for 문에 있는 명령어(if 문)는 만큼 실행된다. if문의 실행 시간을 c1 * n(n-1)/2 교환(exchange)명령의 실행 시간을 c2 * n(n-1)/2 로 ...