시간복잡도, 알고리즘 선택의 기준 - 표기법 알아보기

사망년 이제서야 진지하게 시작하다 :(

 

 

시간복잡도 : 주어진 문제를 해결하기 위한 연산 횟수

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

 

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
	int findNumber;
	srand(time(NULL));
	findNumber = rand() % 100;

	for (int i = 0; i < 100; i++) {
		if (i == findNumber) {
			cout << i;
			break;
		}
	}
}

1~100 사이의 무작윗값을 찾아 출력하는 코드

데이터의 크기 N

시간 복잡도: 빅-오메가(1번), 빅-세타(N/2번), 빅-오(N번)

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

*코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다

최악일 때를 염두해 두는 것이 좋다.