다라다라V
article thumbnail
728x90
반응형

복잡도

시간 복잡도

  • 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계

 

빅오 표기법

  • 알고리즘의 로직이 얼마나 시간이 걸리는지(시간 복잡도)를 표현할 때 사용
  • 입력 범위 n을 기준으로 로직의 반복 정도를 표시
  • 가장 영향을 많이 미치는(=가장 큰) 항만 남김

 

시간 복잡도의 필요성

  • 효율적인 코드 개선을 위해 필요

 

시간 복잡도의 속도 비교

공간 복잡도

  • 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
  • 정적 변수와 동적 변수(재귀적 정의)를 모두 포함

 

자료구조에서의 시간 복잡도

[자료 구조의 평균 시간 복잡도]

자료구조 접근 탐색 삽입 삭제
배열 (Array) O(1) O(n) O(n) O(n)
스택  (Stack) O(n) O(n) O(1) O(1)
  (Queue) O(n) O(n) O(1) O(1)
이중 연결 리스트  (Doubly Linked List) O(n) O(n) O(1) O(1)
해시 테이블  (Hash Table) O(1) O(1) O(1) O(1)
이진 탐색 트리  (BST) O(logn) O(logn) O(logn) O(logn)
AVL 트리 O(logn) O(logn) O(logn) O(logn)
레드 블랙 트리 O(logn) O(logn) O(logn) O(logn)

 

[자료 구조의 최악의 시간 복잡도]

자료구조 접근 탐색 삽입 삭제
배열 (Array) O(1) O(n) O(n) O(n)
스택  (Stack) O(n) O(n) O(1) O(1)
  (Queue) O(n) O(n) O(1) O(1)
이중 연결 리스트  (Doubly Linked List) O(n) O(n) O(1) O(1)
해시 테이블  (Hash Table) O(n) O(n) O(n) O(n)
이진 탐색 트리  (BST) O(n) O(n) O(n) O(n)
AVL 트리 O(logn) O(logn) O(logn) O(logn)
레드 블랙 트리 O(logn) O(logn) O(logn) O(logn)

 

반응형
profile

다라다라V

@DaraDaraV

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!