Big-O 표기법
Big-O
- 서로 다른 알고리즘의 효율을 측정, 비교하기 위한 방법
- 수행되는 연산(산술, 비교 대입) 의 개수를 '대략적으로' 판단
// 수행 횟수: 1
int Add(int n){
return n+n;
}
// 수행 횟수: N² + 1
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;
}
- 영향력이 가장 큰 대표 항목만 남기고 삭제
- 상수는 무시한다.(2N -> N)
// 수행 횟수: N² + 1
// Big-O: 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;
}
// 수행 횟수: N² + 4N + 1
// Big-O: O(N²)
int Add4(int n){
int sum = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sum+=1;
}
}
for(int i=0;i<4;i++){
for(int j=0;j<n;j++){
sum+=1;
}
}
return sum;
}
-
Big-O를 통해 입력 N의 크기에 따라 성능이 영향을 받는 정도를 나타낼 수 있다.
-
ex) 위와 같이 n²의 시간복잡도를 갖는 알고리즘의 경우 데이터가 많은 경우
사용시 효율이 나쁘다. -
ex) logN 의 시간복잡도를 갖는 이진트리 알고리즘의 경우 효율이 좋다.
-
Author And Source
이 문제에 관하여(Big-O 표기법), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sansam41/Big-O-표기법저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)