빅 오 표기법(Big-O)

Min·2020년 12월 30일
0

Algorithm/DataStructure

목록 보기
1/12
post-thumbnail

시간 복잡도

  • 얼마나 빠르게 실행되는지(알고리즘 실행 속도)

공간 복잡도

  • 얼마나 많은 저장 공간이 필요한지(알고리즘이 사용하는 메모리 사이즈)

빅 오 표기법

  • O(입력) : 입력 n 에 따라 결정되는 시간 복잡도 함수

  • Good(Fater)
    O(1) : 스택의 push, pop, 해쉬 테이블의 Access
    O(log₂n) : 이진트리(BST)
    O(n) : Traverse 트리, Traverse 링크드 리스트(for문)
    O(nlog₂n) : 퀵, 병합, 힙 정렬
    O(n²) : 삽입, 버블, 삽입 정렬

  • Bad(Slow)

  • 특징 : 상수항은 무시한다.

profile
slowly but surely

0개의 댓글