시간복잡도 (Big O)

• big-o는 시간의 효율성, 공간의 효율성을 따질 때 많이 쓰이는 개념이다.

프로그램의 성능을 알기 위해 알아야 할 것은?

1. 입력 크기

2. 하드웨어 성능

3. 운영체제 성능

4. 컴파일러 최적화

5. 비동기 로직

   .....

→ 실행 환경과 메모리에 따라 다른 결과가 나오므로 프로그램의 정확한 성능을 알아내기는 어렵다.

⇒ 이를 위해 시간 복잡도를 추상화하여 나타내는 BigO가 등장하였다.

Algorithms Searching and Sorting Algorithm Efficiency 1 Efficiency

Big O 관련 된 샘플코드는 하단 링크를 통해서 확인 해 볼 수 있다.

Understanding Big O Notation via JavaScript | DigitalOcean

특징

• 접근적 표시법을 따른다.

• 추세표를 따르기 때문이다.

• 한없이 가까워질 수는 있지만, 일치할 수 는 없다.

  계수법칙

  • 무한에 가까울수록 상수값들은 의미가 없기 때문에 표기하지 않는다.

  합의법칙

  • BigO끼리는 더해질 수 있다.

  곱의법칙

  • BigO끼리는 곱해질 수 있다.

  다항법칙

  • k차 다항식이면 f(n)은 O($n^K$)

1. 상수항은 무시된다.

2.가장 큰 항 외에는 무시된다.