Algorithm | 시간복잡도 Time Complexity

📝 Programmers School
[C++] 어서와! 자료구조와 알고리즘은 처음이지?

시간 복잡도

시간 복잡도 : 입력의 크기가 커짐에 따라 연산 시간(연산 횟수)이 얼마나 증가하는 지를 근사적으로 표현

빅오 표기법

O(f(n))

• 대표적인 시간 복잡도 표현 방법
• 연산 횟수를 구체적인 수식으로 표현하지 않고 최고차항의 차수만으로 표현
• 점근 표기법의 한 방법 → 실행 시간의 상한 표현

Big O	name	contents
O(1)	상수 함수	입력 크기와 무관하게 일정 시간 소요
O(log n)	로그 함수	입력 크기와 로그에 비례하는 시간 소요 대체로 매 단계마다 입력 크기를 절반으로 줄여가는 형태로 동작
O(n)	선형 함수	입력 크기에 비례하는 시간 소요
O(n log n)	로그-선형 함수	효율적인 정렬 알고리즘 (퀵 정렬)
O(n²)	이차 함수	2중 중첩 반복문 사용
O(n³)	삼차 함수	3중 중첩 반복문 사용
O(2ⁿ)	지수 함수	부분집합 구하기
O(n!)	팩토리얼 함수	순열

예제

return n;

→ n값에 관계 없이 1회 연산 실행 O(1)

for (int i = 0; i < n; i++) {
	sum += data[i];
}

for (int i = 0; i < n; i++) {
	var += (data[i] - mean) * (data[i] - mean);
}

→ 반복문의 복잡도와 관계 없이 for 내부 문장이 2n회 실행 O(n)

for (int i = n - 1; i > 0; i--) {
	for (int j = 0; j < i; j++) {
    	if (data[j] > data[j + 1])
        	swap(data[j], data[j + 1];
        }
    }
}

→ 이중 for 반복문 내부 문장이 1/2*n(n-1)회 실행 O(n²)

int sum(int n) {
	if (n == 1)
    return 1;
    
    return n + sum(n - 1);
}

→ 재귀 함수 n번 호출 + 함수 내부에 단일 연산만 존재 O(n)
→ 재귀 함수 내부에서 재귀를 2번씩 호출하면 O(2ⁿ)