Machineboy空
Ordered Data Structures # WEEK 1 - Run Time Analysis / Array and List Operation 본문
Ordered Data Structures # WEEK 1 - Run Time Analysis / Array and List Operation
안녕도라 2024. 2. 13. 11:151.3 Run Time Analysis
런타임 분석은 입력 데이터의 크기를 늘려가며 어떤 알고리즘이 빠른지 분석하는 기법.
배열의 사이즈를 재조정하는 방법 2가지를 비교해보았음.
- Run-Time Analysis allows us to formalize a method of comparing the speed of an algorithm as the size of input grows.
- We summeraize the runtime in "Big-O notation", leaving only the term that dominates the growth
- O(1), constant time
- approximately same time no matter how many data.
- O(n), linear time
- as data size grows, running time grows at the same rate
- O(n^2), polynomial time (다항식 시간)
- strategy#1 같은 것? O(1), O(n)보다 훨씬 느림
- O(1), constant time
Objective: Access a given index.
- Array의 경우 : just one multiplication no matter how many data in array
- 데이터의 사이즈 * 인덱스를 더해주면 됨
- List의 경우 : 99 에 접근하고자 하면 move 99 times following next pointer.
- as the data grows access time grows
Array Resize Strategy
Objective : Resize an array
- Strategy #1 : When the array is full, add two to the capacity
- actually add up the total number of copies that it takes over the entirety of the algorithm expanding from an initial array of capacity two, all the way down to the when the array is the capacity of two times r.
- Strategy #2 : When the array is full, double the capacity
- Only once every so often do we have to actually then copy over all the data and move forward. But then we can insert all of that data again before we have to do another copy operation
- 실제로 복사가 일어나는 횟수가 strategy1에 비해 훨씬 감소함
1.4 Array and List Operations
Arrays and Lists are both ordered collections of data. There are several key operations common to both all ordered collections that are worth analyzing.
Access a Given Index & Insert element at the front
Objective: Access a given index in the collection
Find Data
Find Data in Sorted Array
Binary Search! sort하고 중간과 비교 또 중간과 비교 이런 식인가봄.
리스트는 중간으로 바로 가는 매직 포인터는 없으므로 처음부터 다 탐색해야함.
Insert After
Objective: Given an element (ListNode or Index), insert a new element immediately afterwords.
Arrays and lists are both ordered collections that have complex tradeoffs(절충점) between run-time and flexibilty.
빠르게 실행해야하는지, 어떤 연산을 할지에 따라 Array를 쓸지 list를 쓸지 고민해야한다.
We will building data structures using these primitive structures.
프로그래밍을 건축에 비유한다면 데이터 구조들은 일종의 벽돌, 그리고 설계가 디자인기법 등이 되려나.
'Computer > 자료구조' 카테고리의 다른 글
Ordered Data Structures # WEEK 2 : Tree 개념& Binary Trees & Tree Traversals 트리순회 (0) | 2024.02.14 |
---|---|
Ordered Data Structures # WEEK 1 - Queue & Stack (1) | 2024.02.13 |
Ordered Data Structures # WEEK1 : Arrays VS Linked Memory 개념 (1) | 2024.02.12 |
Object-Oriented Data Structures # WEEK04 : Inheritance 상속 (0) | 2024.02.07 |
Object-Oriented Data Structures # WEEK04 : Templates and Classes (0) | 2024.02.07 |