시간 복잡도

시간복잡도

---

• 입력 크기에 대해 어떠한 알고리즘이 실해되는데 걸리는 시간
• 주요 로직의 반복 횟수를 중점으로 측정

빅오표기법

---

• 복잡도에 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없애 복잡도를 나타낸는 표기법
  $n! >2^n > n^2 > nlogn > n > logn > 1$

상수 시간 시간 복잡도 O(1)

---

• 입력 크기 상관없이 일정한 시간 복잡도를 가지는 것
• 종류
  • 입출력문: cin, cout, scanf, printf
  • 곱하기
  • 사칙연산
  • 간단한 비교 if문: if(a[2] == 2)
  • 배열의 인덱스 참조 : int a[3] = {1, 2, 3}

자료구조의 시간 복잡도

---

	참조	탐색	삽입/삭제
배열(Array)	O(1)	O(n)
Vector	O(1)	O(n)	맨 끝,앞 삽입/삭제 O(1)
중간 삽입/삭제 O(n)
Doubly Linked List	O(n)	O(n)	O(1)
Stack	n번째 참조: O(n)
가장 앞부분 참조: O(1)	O(n)	(n번째 제외) O(1)
Queue	O(n)	O(n)	O(logn)
Map	O(logn)	O(logn)	O(logn)