• 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수
• 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측

시간 복잡도 유형

• 빅-오메가(Ω(n))
  • 최선일 때(best case)의 연산 횟수를 나타낸 표기법
• 빅-세타(Θ(n))
  • 보통일 때(average case)의 연산 횟수를 나타낸 표기법
• 빅-오(O(n))
  • 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

시간 복잡도 예제 코드

public class timeComplexityExample1 {
	public static void main(String[] args) {
		// 0~99 사이 값 랜덤 선택
		int findNumber = (int)(Math.random() * 100);
		for(int i = 0; i < 100; i++) {
			if(i == findNumber) {
				System.out.println(i);
				break;
			}
		}
	}
}

• Ω(n) = 1
• Θ(n) = N/2
• O(n) = N

빅-오 표기법(O(n))의 시간 복잡도

[000] 수 정렬하기

• 정렬 부분을 학습 완료했고, 버블 정렬과 병합 정렬의 시간 복잡도를 각각 O(n²), O(nlogn)이라고 알고 있다고 가정
• https://www.acmicpc.net/problem/2751