Big-O 표기법 사용이유
알고리즘의 성능 비교를 위해 Big-O 표기법을 사용한다
Big-O 표기법 사용법
1단계. 대략적인 계산
2단계. 최고차항 계수만 남기고 상수도 버린다
Big-O 표기법 사용법 예시
int Add(int n)
{
return n + n;
}// O(1)
int Add2(int n)
{
int sum = 0;
for(int i = 0; i < n; i++)
{
sum += i;
}
return sum;
}// O(N)
int Add3(int n)
{
int sum = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
sum += 1;
}
}
return sum;
}// O(N^2)
int Add4(int n)
{
int sum = 0;
for(int i = 0; i < n; i++)
{
sum += i;
}// O(N)
for(int i = 0; i < 2 * n; i++)
{
for(int j = 0; j < 2 * n; j++)
{
sum += 1;
}
}// O(4N^2)
sum += 1234567;// O(1)
return sum;
}// O(4N^2 + N + 1) -> O(N^2)
Big-O 표기법 그래프
log 함수
로그 함수는 매번 절반 씩 줄어드는 것이 핵심이다
또한, 프로그래밍에서 밑은 대부분 2이기 때문에 생략을 해서 표현한다
'자료구조 & 알고리즘 > [루키스] C++ 자료구조 & 알고리즘' 카테고리의 다른 글
[C++ 자/알 Note] 스택 구현 (0) | 2025.01.08 |
---|---|
[C++ 자/알 Note] 연결리스트 구현 (0) | 2025.01.08 |
[C++ 자/알 Note] 동적배열 구현 (0) | 2025.01.07 |
[C++ 자/알 Note] 배열, 동적배열, 연결리스트 (0) | 2025.01.04 |
[C++ 자/알 Note] 오른손 법칙 (미로 탐색) (0) | 2025.01.04 |