Big-O 표기법과 알고리즘의 스피드

빠른 알고리즘은 느린 알고리즘보다 우수하다!

하지만... 빠름과 느림의 종류는 굉장히 다양하다. 알고리즘의 스피드를 어떻게 전문으로, CS적으로 표현하면 좋을까?

두 가지 알고리즘을 비교하는 방법?

• A가 B보다 "조금", "많이" 빨라요 -> 애매모호함.
• 어떤 환경에서는 a가 빠르고, 어떤 환경에서는 b가 빠르다면 애매하고 무의미해짐. 즉 시간으로 표현해서는 안됨.
  ex) 내 컴퓨터는 최신 컴퓨터라 너의 컴퓨터에서보다 알고리즘 실행이 빠르다.
• 입력이 적은 구간과 많은 구간 사이에서 성능 차이가 확연히 나는 경우도 있음
• ex) 출퇴근 할 때 지하철이 빠른가 버스가 빠른가? 회사가 가까울 경우 버스가, 거리가 멀 수록 지하철이 좋은 선택이 되는
         경우와도 같음. 두 가지 경우가 강점을 보이는 경우가 다른 상황이 있을 수 있다는 것.
• 따라서 알고리즘의 스피드는 완료까지 걸리는 절차(step)의 수로 결정된다.

Big-O 표기법

: 알고리즘 A와 알고리즘 B를 객관적으로 비교해 보기 위한 방법이다. 알고리즘의 효율성을 표기해준다. 
보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 된다.

규칙 1단계 : 대략적인 계산
- 수행되는 연산(산술,비교 대입 등)의 개수를 '대략적으로' 판단한다.

규칙 2단계 : 대장만 남긴다
1)  영향력이 큰 항목만 남긴다
2) 상수 무시 (ex. 2N -> N)
ex) O(1 + N + N² + 1) = O(4*N²) = O(N²)
거시적인 관점에서 제곱에 비해서 상수는 영향력이 미미하다.

BIG-O 표기법의 의의

: 입력 N의 크기에 따라 성능이 영향을 받는 정도를 나타냄.

가로축n: 데이터량 / 세로축t: 시간

 

https://cooervo.github.io/Algorithms-DataStructures-BigONotation/index.html

 속도차이를 비교해보면 n² 은 가장 느린 속도 나쁜 성능을 보여주고,
log n 의 경우 가장 빠른 성능을 보여준다.  물론 1의 경우가 가장 빠르다.