시간 복잡도

시간 복잡도

• 주어진 문제를 해결하기 위한 연산 횟수
• 보통 빅-오(O(n)) 표기법을 기준으로 수행 시간을 계산 → 항상 최악일 때(데이터의 크기가 가장 클 때)를 기준

시간 복잡도 유형

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

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준

 

예제1) 연산횟수 = N

#include<iostream>
using namespace std;

int main()
{
int n=1000;
int cnt=1;

for(int i=0;i<n;i++){
    cout<<"연산 횟수: "<<cnt++<<endl;
	}
}

예제2) 연산횟수 = 3N

#include<iostream>
using namespace std;

int main()
{
int n=1000;
int cnt=1;

for(int i=0;i<n;i++){
    cout<<"연산 횟수: "<<cnt++<<endl;
	}
    
for(int i=0;i<n;i++){
    cout<<"연산 횟수: "<<cnt++<<endl;
	}
    
for(int i=0;i<n;i++){
    cout<<"연산 횟수: "<<cnt++<<endl;
	}
}

위의 두 예제의 연산 횟수는 3배 차이이나

시간 복잡도를 계산할 때, 상수를 무시하므로 두 코드의 시간 복잡도는 O(n)으로 같다.

 

예제3) 연산 횟수 = N^2

#include<iostream>
using namespace std;

int main()
{
int n=1000;
int cnt=1;

for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
    		cout<<"연산 횟수: "<<cnt++<<endl;
    }
    }
}

예제 3에서는 이중 for문이 사용되었다.

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 시간복잡도는 N^2이다.