빅오표기법 (big-O)

Big-O란 무엇인가?

• 알고리즘 성능을 수학적으로 표기해주는 표기법
• 시간과 공간 복잡도를 표현
• 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는게 목표, 상수와 같은 숫자들은 모두 1이 된다.

시간복잡도

• 시간복잡도란 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수를 말한다.
• 알고리즘을 평가하는데 있어 수행시간과 메모리 사용량을 평가기준으로 두는데
  • 수행시간에 해당하는 것이 시간 복잡도 Time Complexity
  • 메모리 사용량에 해당하는 것이 공간 복잡도 Space Complexity

연산 횟수를 카운팅 할때 3가지 경우가 있다.

1. 최선의 경우 Best Case
2. 최악의 경우 Worst Case
3. 평균적인 경우 Average Case

빅오표기법 예제

O(1)

• constant time
• 입력 데이터 크기에 상관없이 일정한 시간이 걸리는 알고리즘을 표현

O(N)

• linear time
• 입력 데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘을 표현

O(N**2)

• quadratic time
• 입력 데이터가 커지면 커질수가 처리시간의 부담도 커지게 된다

O(N**3)

• polynomial / cubic time
• N squre와 비슷한 양상이지만, 데이터가 늘어남에 따라 가로세로 높이까지 늘어나기 때문에, 더 가파르게 올라갑니다.

O(2**n)

• exponential time
• Fibonacci와 관련, 데이터의 증가에 따라 시간이 현저하게 늘어납니다.

O(log n)

• 대표적 알고리즘 : binary search
• 한번 처리가 진행될때마다 검색해야하는 데이터의 양이 절반씩 떨어지는 알고리즘입니다
• 데이터가 증가해도 성능에 크게 차이나지 않습는다.

빅오 표기법 특징

상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시합니다.

 

정렬

시간복잡도 O(n²) 정렬 알고리즘

• 버블(bubble) 정렬
• 선택(Selection) 정렬
• 삽입(Insertion) 정렬

시간복잡도 O(nlogn) 정렬 알고리즘

• 병합(Merge) 정렬
• 힙(Heap) 정렬
• 퀵(Quick) 정렬

 

 

출처: 

https://noahlogs.tistory.com/27

https://www.youtube.com/watch?v=6Iq5iMCVsXA

https://velog.io/@kimhyo_0218/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B3%B5%EB%B6%80-%EC%8B%9C%EC%9E%91%ED%95%98%EA%B8%B0