빅오 big-O

빅오 표기법

 

• 서로 간의 시간복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하게 일관된 언어로 설명하기 위한 수학적 언어이다.
• 빅오 표기법을 이용해 주어진 알고리즘의 효율성을 쉽게 분류하고 이해 할 수 있다.
• 표기 : O(N)

빅오의 실행 속

• O(1) → O(log N) → O(N) → O(N log N) → O(N^2) → O(N) → O(2^N)
• 아랫단계에 어떤 수를 곱하든 데이터가 커지다 보면 언젠가 윗 단계가 더 느려진다.

빅오의 N단계

• 빅오의 표현은 괄호 안에 있다.
• O(1)은 가장 빠른 알고리즘으로 분류한다.
• 데이터가 늘어나도 단계수는 증가하지 않는다.
• N이 얼마든 항상 상수단계에서만 필요하다.

 

빅오의 본질

• 데이터가 늘어날때 알고리즘의 성능이 어떻게 바뀌는지가 관건이다.
• 데이터 증가에 영향을 받지 않으면 구분할 필요가 없다

→ O(1) == O(3)

• 효율성을 따질때는 대부분 최악의 시나리오로 구분한다.

로가리즘

• log의 줄임말이다
• 지수(exponent)와 역(inverse)의 관계이다.
• 2의 3제곱 = 2 x 2 x 2와 동치이다. 값 : 8

 

O(logN)의 해석

• O(logN)은 사실 O(log2N)을 줄여서 표기 한 것이다.
• 데이터 원소 N개가 있을때 log2N 단계가 걸린다는 의미이다.
• O(logN)은 원소가 하나가 될때까지 데이터 원소를 반으로 줄이는 만큼의 단계가 걸린다.