[Kmooc] 중간고사 정리

본 게시글은 Kmooc-자료구조 수업의 중간고사를 기반으로 정리함.

 

시간복잡도 : n^100 < 2^n < n! < n^n

정렬되지 않은 배열에서 삽입 :  O(1)

정렬되지 않은 연결 리스트에서 삭제 : O(n)

정렬된 배열에서 이진 탐색 (binary search) : O(log n)

버블 정렬 : D(n^2)

 

성능을 측정할 때 보장의 의미를 부여하기 위해서 선택하는 성능 : 최악의 경우의 성능

 

f(n) = O(n^2)에 대한 설명

• f(n)은 어떤 경우에도 n3보다 빠르다.
• f(n)의 최악의 경우는 n2이다.
• f(n)의 상한은 n2이다.
• f(n)은 n2보다 성능이 더 좋다.

배열

• 연속적으로 할당된 기억 공간에 저장된다.
• 배열의 모든 원소들은 인덱스에 대응된다.
• n 개의 자료를 하나의 주소로 접근할 수 있다.