| English | 의미 |
|---|---|
| Big-O/bɪɡ əʊ/ | Big-O 표기법 |
| time complexity/taɪm kəmˈpleksɪti/ | 시간 복잡도 |
| space complexity/speɪs kəmˈpleksɪti/ | 공간 복잡도 |
| depth-first/depθ fɜːst/ | 깊이 우선 |
| breadth-first/bredθ fɜːst/ | 너비 우선 |
| binary tree/ˈbaɪnəri triː/ | 이진 트리 |
The algorithm that would outlive the universe
- A salesman must visit 25 cities and return home by the shortest route. Try every order and there are about $10^{23}$ of them. A machine checking a billion a second would take three million years.
- Add one more city and the work multiplies by 25. That is not a computer that needs to be faster; it is an approach that can never work, at any speed, on any hardware.
- Knowing that before you write the program is what complexity analysis is for. It is the difference between choosing an algorithm and discovering, months later, that yours does not scale.
- This lesson is Big-O 大O表示法 for time and space, and how ADTs shape the algorithms built on them.
Time complexity
- Time complexity 时间复杂度 describes how the running time grows with the input size $n$. It is written in Big-O notation, which keeps only the dominant term and drops constants.
- $O(1)$ constant, the time does not depend on $n$ at all. $O(\log n)$ logarithmic, as in binary search. $O(n)$ linear, as in linear search. $O(n \log n)$, the good sorts. $O(n^2)$ quadratic, as in bubble and insertion sort.
- The reason constants are dropped: they are swamped. An $O(n^2)$ algorithm might beat an $O(n \log n)$ one for $n = 10$, but at $n = 10{,}000$ nothing about the constants can save it.
The curves cross once, and after that the order decides everything
n에 따른 실행 시간의 성장 양상
n을 위쪽으로 슬라이드하며 곡선을 비교해 보십시오: O(1)과 O(log n)은 거의 평평하게 유지되고, O(n)은 일정하게 상승하며, O(n²)는 급격히 폭발합니다. 이것이 Big-O가 시계로 측정하는 것이 아니라, 대규모 입력에서 알고리즘을 비교하는 기준이 되는 이유입니다.
이진 검색을 설명하는 Big-O는 무엇입니까?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
단계마다 범위를 반으로 줄이는 것은 로그 함수적이며, O(log n)입니다.
최악의 경우 버블 정렬을 설명하는 Big-O는 무엇입니까?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
n개 요소를 두 번 중첩된 루프로 순회하면 O(n²)가 됩니다.
각 알고리즘을 시간 복잡도에 매칭하세요.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
선형 검색은 O(n), 이진 검색은 O(log n), 버블 정렬은 O(n²)입니다.
Worked example: what doubling the input does
- An algorithm takes 4 seconds on 1,000 items. Estimate its time on 2,000 items if it is $O(n)$, then if it is $O(n^2)$.
- $O(n)$: doubling $n$ doubles the time, so about 8 seconds.
- $O(n^2)$: doubling $n$ quadruples the time, so about 16 seconds. At 10,000 items it would be 100 times the original, about 400 seconds.
- $O(\log n)$ would add only a single step, and $O(1)$ would not change at all. Reason from the order, not from a formula.
O(n²) 알고리즘은 ⟨4⟩개의 항목에 대해 ⟨1,000⟩초를 소요합니다. ⟨2,000⟩개 항목에서는 대략 몇 초가 걸릴까요?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
n을 두 배로 늘리면 O(n²) 알고리즘의 실행 시간은 네 배가 됩니다. 같은 두 배 증가로 O(n) 알고리즘은 4초에서 8초로 바뀝니다.
Space complexity
- Space complexity 空间复杂度 is the extra memory an algorithm needs, beyond the input itself.
- Bubble and insertion sort use $O(1)$ extra memory: they work in place, needing only a couple of variables. Merge sort uses $O(n)$, since it builds a second array.
- Recursion uses stack memory proportional to its depth, because every unfinished call keeps its own frame.
- There is often a time and memory trade-off: storing results to avoid recomputing them, as memoisation does, buys speed with space.
What else decides the choice
- Big-O is about growth, not absolute speed. For a small $n$, a simple $O(n^2)$ algorithm can beat a complicated $O(n \log n)$ one, and it is easier to write correctly.
- Stability matters when a list is already ordered by another field. Simplicity matters because a simple algorithm has fewer places to hide a bug.
- The honest answer to "which algorithm" often names the order and the conditions: this one, because $n$ is large and the data arrives unsorted.
"in place" 정렬:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
in-place 알고리즘(버블 정렬 및 삽입 정렬 등)은 상수 수준의 추가 공간만을 사용하여 원본 배열 내에서 정렬을 수행합니다.
버블 정렬이 n개의 요소를 정렬함에도 불구하고 왜 공간 복잡도가 O(1)입니까?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
이것은 in-place로 정렬합니다. 병합 정렬은 두 번째 배열을 구축하므로 O(n)이며, 재귀는 그 깊이와 비례하는 메모리를 소모합니다.
ADTs inside algorithms
- The abstract data types from topic 10 are the machinery algorithms are built from, and choosing one shapes the algorithm.
- A stack gives depth-first 深度优先 search: push the neighbours, take the most recent, and the search plunges down one path before backing up. Recursion uses the call stack for exactly this.
- A queue gives breadth-first 广度优先 search: enqueue the neighbours, take the oldest, and the search spreads outward in rings, which is what finds the shortest path in an unweighted graph.
- A binary tree 二叉树 keeps values in order so that a search discards half the remaining nodes at each step, giving binary search's $O(\log n)$ over a structure that can also grow.
Big-O에 대한 다음 중 올바른 진술을 모두 선택하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
Big-O는 초에 대해 말하지 않으며, 성장 양상에 관하여 말합니다. 이것이 단순한 알고리즘과의 교차점이 작은 크기에서 발생하는 이유입니다.
Worked example: the same graph, two searches
- A maze is explored from one entrance. Contrast using a stack with using a queue.
- With a stack, the most recently found path is explored next, so the search goes deep down one route until it dead-ends, then backtracks. It uses memory proportional to the depth of the path.
- With a queue, the oldest found path is explored next, so the search examines everything one step away, then everything two steps away. It finds the shortest route first, but holds every position at the current distance in memory.
- Name the ADT, name the resulting order of exploration, and name the consequence.
스택(LIFO)은 naturally 깊이 우선 탐색을 유도하고, 큐(FIFO)는 너비 우선 탐색을 유도합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
선택한 ADT가 검색 순서를 결정합니다: 스택은 깊게 먼저, 큐는 층별로 확장합니다.
각 ADT를 생성하는 검색 유형과 그 결과로 매칭하세요.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
가장 최근 또는 가장 오래된 것부터. 이 단일 선택이 검색이 깊게 가거나 넓게 가를 결정합니다.
Marks that slip away
- Big-O describes growth with input size, not seconds. "It is fast" is not a complexity answer.
- Doubling the input doubles an $O(n)$ time and quadruples an $O(n^2)$ one. Reason from the order.
- Space complexity is the extra memory, which is why an in-place sort is $O(1)$ even though the array is size $n$.
- Stack gives depth-first, queue gives breadth-first. Getting that pair the right way round is the whole of several questions.
You've got it
- time complexity in Big-O describes growth with $n$: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$; constants are dropped because at scale the order decides
- doubling $n$ doubles $O(n)$ and quadruples $O(n^2)$; the crossover with a "worse" algorithm only exists for small $n$
- space complexity is the extra memory: in place sorts are $O(1)$, merge sort is $O(n)$, and recursion costs stack depth
- a stack gives depth-first search, a queue gives breadth-first, and a binary tree halves the remaining nodes at each step