3. Unsorted List and Sorted List

생성일: 2021년 9월 10일 오후 9:37

List Definitions

• Linear relationship(1차원 관계) 제일 처음 element와 끝 element를 제외하면 모든 element들은 unique predecessor와 successor을 가진다.
  
• Length The number of items in a list
  
• Unsorted list No particular order list
  
• Sorted list sorted by the value in the key
  
• Key The attribute that are used to determine the logical order of the list
  

Unsorted List 구현

Sorted List

• Unsorted List와 비교 했을 때 InsertItem과 DeleteItem 함수가 달라져야한다.

Sorted List 구현

Comparison of Algorithms

어떤 알고리즘이 더 좋은 것일까?

• Objective measures for efficiency
  • Execution time
  • Number of statements
  • Number of fundamental operations

Big-O notation(order of magnitude)

최악의 경우에서의 실행 횟수를 측정

$f(n) = n^4+100n^2+10n+50$

⇒ $O(n^4)$

Big-O Comparison of List Operations

InsertItem과 DeleteItem의 경우 Binary search를 사용하게 되면 해당 item을 넣거나 지울 자리를 찾기위해 $O(\log_2N)$과 insert 혹은 delete 이후 나머지 요소들의 자리 수정을 위해 $O(N)$이 필요하다. 즉 $O(\log_2N)+O(N)$ 이다. 따라서 그냥 Sequential search인 $O(N)$보다 나을 것이 없다.