시간복잡도 란?

알고리즘의 효율성은

-알고리즘의 수행시간 (시간복잡도, Time Complexity)
-수행하는동안 사용되는 메모리 공간의 크기 (공간복잡도, Space complexity)

로 나타낼 수 있다.

사용되는 메모리, 공간등은 주어진 환경에 따라서 다르기 때문에 보통 알고리즘을 비교할때는
시간복잡도로 표현한다.

시간복잡도는 알고리즘의 수행하는 기본적인 연산의 횟수를 입력의 크기에 대한 함수로 표현한다.

ex) 크기가 N인 데이터를 순차적으로 비교 한다면 총 비교 횟수는 (N-1)이 되므로크기가 N인 순차적인 알고리즘의 시간복잡도는 (N-1)이다.

시간복잡도는 표현할때는 3가지의 분석 방법이 주어지는데
1. 최악의 경우 분석 (Worst Case Analysis)
2. 평균의 경우 분석 (Averge Case Analysis)
3. 최선의 경우 분석 (Best Case Analysis) 로 나누어 진다.

일반적으로 나타낼때는 최악의 경우로 복잡도를 나타낸다  가장 최악의 경우이므로 더 나빠질 수가 없기 때문에..

순차적인 알고리즘을 예로 들어볼때 1,2,3,4,5 의 배열에서 숫자를 찾는다고 가정하면
숫자 5를 찾을때는 1  2  3 4  5 까지 총 4번의 순차적인 과정이 있었기 때문에 최악의 경우로 볼 수 있다.
만약 숫자 1을 찾을때는 1에서 한번의 비교로 찾게되며 이 경우는 최선의 경우로 볼 수 있다.
숫자 3을 찾는 경우 평균의 경우로 볼 수 있으며

자료의 양과 찾는 데이터의 값에 따라 최선,최악의 과정의 값이 차이가 많이 나게 된다.

운이 좋으면 한번만에 찾을 수도 있고 안좋으면 마지막까지 비교를 해야된다.

시간복잡도는 입력 크기에 대한 함수로 표기하는데 이때 함수는 복잡한 식을 가진 다항식으로서 표현 될 수 있다.
이때 복잡한 식을 간단하게 표현하기 위해 표시할때는 점근적 표기(Asymptotic notation)를 사용한다.

고등학교때 배운 n이 무한대로 갈때 극한을 생각하면 이해하기가 편할것같다.

크기가 최대라고 가정할때 식에서 최고차항만 계수없이 취하고 나머지는 다루지 않는다.
이러한 표현을
- O (Big-Oh), 빅오 - 표기라고 한다.