1. 시간 복잡도

• 실행 시간은 실행 환경에 따라 달라짐
• 실행 시간을 측정하는 것이 아니라 연산 실행 횟수를 세는 것으로 판단함
• 연산 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현됨 (실행 횟수에 따른 데이터 크기)
• 데이터의 크기가 같더라도 실제 데이터에 따라 달라짐.
  • 최악의 경우 시간 복잡도 worst case
  • 평균 시간 복잡도 average

2. 점근적 분석 (Asymptotic)

• 점근적 표기법: 데이터의 개수가 n → ∞ 일 때 수행 시간이 증가하는 growth rate로 시간 복잡도를 표현하는 기법
• Big O라고들 부름
• 유일하거나 가장 좋은 분석법은 아니나 간단하고 실행환경을 고려하지 않고 측정하기 편하기 때문에 보편적으로 쓰임

2.1 상수 시간복잡도 - O(1)

n개의 데이터가 저장된 배열이 주어지고, 그 중 n/2 번째 데이터를 반환한다고 가정

public int sample(int[] data, int n){
	int k = n / 2;
	return data[k];
}

데이터의 크기, n의 크기와 상관 없이 항상 n / 2 를 측정하므로 상수 시간이 소요. O(1)라고 표기한다.

2.2 선형 시간 복잡도 - $O(n)$