빅오 표기법(Big O Notation)
Big O?
여러 문제 해결 방법 중 무엇이 가장 좋은 지 알 수 있다. 코드의 일반화를 통해 분류된 이름을 붙힌다.
Big O Notation?
애매한 측량을 정형화한 방법. 알고리즘에 입력값이 커짐에 따라 실행시간이 늘어나는 정도의 관계. 추세에만 신경쓰는 것! (세세한 부분은 넘어간다.)
- N이 증가함에 따라 컴퓨터가 수행해야하는 단순 동작의 수가 상수로 수렴하는 f(n)보다 작은 값이 된다면 알고리즘이 O(n)이라고 부른다.
f(n) = n // 직선
f(n) = n^2 // 2차함수
f(n)= 1 // 일정한 값
여러 문제 해결 방법 중 무엇이 가장 좋은 지 알 수 있다. 코드의 일반화를 통해 분류된 이름을 붙힌다.
애매한 측량을 정형화한 방법. 알고리즘에 입력값이 커짐에 따라 실행시간이 늘어나는 정도의 관계. 추세에만 신경쓰는 것! (세세한 부분은 넘어간다.)
- N이 증가함에 따라 컴퓨터가 수행해야하는 단순 동작의 수가 상수로 수렴하는 f(n)보다 작은 값이 된다면 알고리즘이 O(n)이라고 부른다.
f(n) = n // 직선
f(n) = n^2 // 2차함수
f(n)= 1 // 일정한 값
ex) 1부터 n까지의 합을 만드는 함수
1. O(n) operations의 개수가 n의 배수와 관련이 있다.
function addUpTo(n){
let total = 0;
for(let i = 1; i <n; i++{
total++;}
return total; }
2.O(1) 항상 3개의 operations
function addUpTo(n){
return n*(n+1)/2;}
ex) 또 다른 예시
function countUpAndDown(n){
console.log('Going Up!");
for(let i =0; i<n; i++){
console.log(i);}
console.log('At the top! Going down...');
for(let j = n -1; j >=0; j--){
console.log(j);
console.log('Back down. Bye!');}}
O(n)이 몇 개이든 trend가 중요하기 때문에 그냥 O(n)이다.
ex) 또 다른 예시 - O(n^2)
function printAllPairs(n){
for(let i =0; i<n; i++){
for(let j =0; j<n; j++){
console.log(i,j);} } }
시간 복잡도 Big O 표기법 단순화 하기
눈대중 규칙
1. 상수는 신경쓰지 않는다.
O(2n) ❌ O(n) ⭕️
O(500) ❌ O(1) ⭕️
O(13n^2) ❌ O(n^2) ⭕️
2. 더 작은 단위는 신경쓰지 않는다.
O(n + 10) ❌ O(n) ⭕️
O(100n + 50) ❌ O(n) ⭕️
O(n^2 + 2n) ❌ O(n^2) ⭕️
ex) O(n)
logALeast5(n){
for(let i = 1; i<=Math.Max(5,n); i++){
console.log(i);
}
}
ex) O(1) - 5 아래의 숫자만 신경쓰면 되므로 n은 상관이 없다.
logAMost5(n){
for(let i = 1; i<=Math.Min(5,n); i++){
console.log(i);
}
}
공간복잡도
눈대중 규칙
1. 대부분의 primitives(booleans, numbers, undefined, null) are constant space.
2. strings는 O(n)space이다. (n은 string의 길이를 뜻한다.
3. Reference type(객체와 같은) 은 O(n) space 이다. (n은 배열의 길이 객체에서는 key의 갯수를 말한다.)
ex) O(1) Space - n이 상관없다.
function sum(arr){
let total = 0;
for(let i = 0; i < arr.length; i++){
total += arr[i];}
return total;
}
ex) O(n) Space - arr의 길이가 중요하다.
function double(arr){
let newArr = [];
for(let i = 0; i < arr.length; i++){
newArr.push(2 * arr[i]);
return newArr;
}
로그와 색션 재생
logarithms => 지수를 반대로 한 것
log2(8) = 3
log2(value) = exponent => 2^exponent = value
Author And Source
이 문제에 관하여(빅오 표기법(Big O Notation)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hoje15v/빅오-표기법Big-O-Notation저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)