<aside> 📌 입력의 크기 n에대한 연산시간의 근사값 = 효율성을 판단하는 척도
</aside>
| 빅오표기법 |
|---|
| 최고차항의 차수로만 표시 |
| ex:) 4n^2 + 2n + 5 = O(n^2) |
| O(1) | 상수함수 | 입력과 상관없이 시간 소요 | |
|---|---|---|---|
| O(LogN) | 로그함수 | 매 단계마다 입력의 크기가 절반 | |
| O(N) | 선형 함수 | 입력만큼 시간 소요 | 이분탐색 |
| O(N*LogN) | 로그-선형 함수 | 대부분의 효율적인 알고리즘 | 병합정렬, 퀵정렬 |
| O(N^2) | 이차 함수 | 이중반복문 | 버블정렬,선택정렬,삽입정렬 |
| O(N^3) | 삼차 함수 | 삼중반복문 | |
| O(2^N) | 지수 함수 | 여기부터는 효율이 안좋음 | |
| O(N!) | 팩토리얼 함수 | 효율 안좋음 |
<aside> 📌 for문 안에서 if문으로 비교하는 경우 최선의경우 O(1) 최악의 경우 O(N)이 될 수 있음
</aside>
<aside> 📌 재귀함수의 경우 함수 내에서 함수가 몇번 호출되는지 & 루프의 개수 등에 따라 유동적임
</aside>
#include <iostream>
using namespace std;
int main(){
func(3);
}
void func(int n){
if(n==1) return;
func(n-1);
func(n-1);
}
위의 재귀함수 실행시 1→2→4→8. . .번의 func가 호출됨 총 실행횟수는 2^N - 1 이고 = O(2^N)