알고리즘 Big O

김태인·2022년 9월 5일
0

알고리즘

목록 보기
4/9
post-thumbnail

알고리즘의 스피드는 "빠르다", "느리다" 등으로 표현하지 않는다.
컴퓨터라는 하드웨어가 속도를 결정하기때문에 이러한 표현보단 5스텝, 10스텝 등의 "완료까지 걸리는 절차의 수"로 속도를 표현한다

BigO의 장점

  • 시간복잡도를 빠르게 설명할 수 있음
  • 읽기 쉽고, 바로 설명이 가능함
  • 알고리즘 분석을 빠르게 할 수 있음
  • 언제 어떤 알고리즘을 쓰는것이 효율적일지 빠르게 파악이 가능

BigO의 종류

  • Constant Time (상수 시간) = O(1)
  • N이 얼마나 크든 상관없이 끝내는데 동일한 숫자의 스텝이 필요함
  • 항상 선호되는 알고리즘이나, 모든 알고리즘을 상수 알고리즘으로 짜긴 어려움

선형(Linear Search)검색의 시간복잡도 = O(N)

  • 배열이 커지면 필요 스텝이 커지는 알고리즘

Quadratic Time 2차 시간 = O(N^2)

  • 루프안에 루프를 실행시키는 알고리즘
  • 인풋의 n^2

Logarithmic Time (로그시간) / 이진검색(Binary Search) 알고리즘 = O(log N)

  • 로그(logarithm)는 지수(exponent)의 정 반대
  • 이진검색은 정렬되지 않은 배열엔 사용 불가






총 그림 정리 (이 외에도 BigO표기법은 많다)

참조 유튜브 : https://www.youtube.com/watch?v=BEVnxbxBqi8
profile
코딩이 취미가 되는 그날까지

0개의 댓글