여기에 정리할 요약 노트의 원 강의는 MIT 6.006 Introduction to Algorithms, Spring 2020이다.
Interface, or API, is the specification of what you want to do, or in other words, what data you can store and data structure is the representation of how you do it. Algorithms are needed to support data structure operations. In short, interface is a problem set and algorithms are the solution to the problem
Interfaces
A static sequence interface has a fixed number of items it can store. The solution to the static sequence interface is a static array/list. Memory is an array of w-bit words and array is a consecutive chunk of memory. Thus, to access the array[i] is to access (the address of the array in memory + i), making the array access is constant time of O(1)
💡 O(1) per get_at/ set_at/ len O(n) per build/ iter_seqA dynamic sequence interface’s main focus is to insert at or delete from the middle of an array. On top of that, ways to insert/delete at before the beginning and/or after the end should be devised
Data Structures
The two main data structure approaches/tools are arrays and pointers
Linked List
Inserting/deleting is easy as you only need to add/remove a node and change where the pointer of the node right before it points to, hence O(1) time. However, get_at/set_at(ith element) or inserting/deleting the ith element can be anywhere from θ(i) to θ(n) as you have to follow the pointers till you find the element. If you make your linked list store a tail, or a pointer to the last node, deleting the last element will also take a linear time. Whenever a change is made to the linked list, the tail should also be updated
Static Array
Inserting/deleting can’t be achieved by shifting all the elements that will come after the newly inserted/deleted element as the size of a static array is fixed. This is because when a static array is created, it is allocated a certain size of array in memory and by adding an element and thus increasing the size of the array, it can touch other neighboring arrays in memory that it shouldn’t have met. Thus, the only way to achieve this is to create a new array of size n + 1 and copy the elements from the original array into the new array and this will take a linear time
Dynamic Array (Python lists)
It has the size of roughly n, meaning it is θ(n) and is bigger or equal to n, which means it can be n, 2n, 10n, etc. As its size is not strictly n, there will be items to store a sequence and also, some blank ones in the end. The array will keep track of the length to tell where the blank ones start and the size of the array, occupied and blank ones put together. Thus, insert_last(x) takes a linear time and is possible unless n (interface size) = size (representation size). When n = size, you have to allocate a new bigger array and copy the elements into it just like with static arrays but much less often
