여기에 정리할 요약 노트의 원 강의는 MIT 6.006 Introduction to Algorithms, Spring 2020이다.
Sets
A set interface is a container that stores a sequence of iterable entities. A stored item can be retrieved with its key as every item is associated with a unique key
It can be implemented into an unordered array but it will be very inefficient as you’ll have to iterate the whole array to find an item till you run across the item. With an sorted array, the keys of each item being sorted in this case, finding items with keys is faster but it generally takes more time to sort the keys than to build an unordered array
Sorting
In goes an array of n numbers/keys and out comes a sorted array in sorting
Permutation Sort
Enumerate all the permutations of the input array(Ω(n!)) and check which permutation is in order(O(n)). Thus, this algorithm takes at least Ω(n! x n) time
Selection Sort
At each step, find the biggest item in the array and swap it out with the last item in the array. Repeat till the array is ordered. The amount of time this algorithm takes is T(n) and it is the same as T(n-1) + θ(n) as each step takes O(n) and the algorithm is recursive in that you get to sort one less element than the prior step. So sorting will take O(n²) time
💡 Let’s assume T(n) = cn² (c is a constant that doesn’t depend on n) As we think T(n) = T(n-1) + θ(n), we can rewrite it as cn² = c(n-1)² + θ(n) = cn² - 2cn + c + θ(n) Thus, θ(n) = 2cn -c = O(n)Merge Sort
First, you see every element as an array of size 1, which is naturally sorted. Then, merge the array with the one right next to it and sort the elements in order. Repeat till you have one big list whose elements are in order. The merging process per each step takes θ(n) as you have to go through every element to sort them in order. The whole algorithm takes
💡 It takes θ(n) to sort an array of size 1 so: T(1) = θ(n) T(n) = 2T(n/2) + θ(n) because two subarrays merge to become one, and each subarray is half the size of the original big list and it takes θ(n) to merge two subarrays Let’s assume T(n) = θ(n log n) Let’s substitute it w/ cn log n = 2c n/2 log n/2 + θ(n) cn log n = cn(log n - log 2) + θ(n) θ(n) = cn log 2 both are constants so it checks out