ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Big-O 표기법
    Data Structure & Algorithm 2022. 3. 20. 23:32

    Big-O 표기법이란?

    시간복잡도를 나타내는 방법 중 하나


    Big-O 복잡도

    https://www.hackerearth.com/practice/notes/big-o-cheatsheet-series-data-structures-and-algorithms-with-thier-complexities-1/

    • O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
    • n이 모두 같은 수일 때 위의 순서로 복잡도가 높아지며 수행 시간이 늘어남(성능이 떨어짐)

    Big-O 표기법 4법칙

    Big-O 표기법은 점근적 표기법을 따름
    따라서 상수를 더하거나 곱하는 등의 표기를 따로 하지 않음
    물론 실제 계산에서는 상수에 따라 성능이 달라질 수 있음

    • 계수 법칙
      n이 무한에 가까울수록 상수(k)의 의미가 없어지기 때문에 계수를 생략
    • 합의 법칙
      Big-O 간 합산 가능
    • 곱의 법칙
      Big-O 간 곱셈 가능
    • 다항 법칙
      특정 함수가 3차 다항식이면 해당 함수의 Big-O 복잡도는 O(n³) 이 됨

    정리

    아래 두 항목이 가장 큰 특징

    • 상수항 무시 O(7n + 4m) => O(n + m)
    • 가장 큰 항 외엔 무시 O(n² + n) => O(n²)

    Javascript 에서 성능 측정하는 두 가지 방법

    • Date.getTime()
    • console.time(), console.timeEnd()

    'Data Structure & Algorithm' 카테고리의 다른 글

      (0) 2022.03.24
    스택  (0) 2022.03.23
    객체  (0) 2022.03.21
    배열  (0) 2022.03.20
    자료구조란?  (0) 2022.03.20

    댓글

Designed by Tistory.