---
hackmd:
url: https://hackmd.io/m12bxnckRt-rwLdBRe2AhA
title: Untitled
lastSync: 2025-06-02T07:12:28.538Z
---
| **DS** | **ALG** | **Concept** |
| ----------------------------------------------------------------------------------------------------- | ------------- | ------------------- |
| [Linked List](https://www.notion.so/Linked-List-f62ee5e07e3148c6aca6abf7e0a22c28?pvs=21) | BFS | Bit Manipulation |
| [Stacks, Queues](https://www.notion.so/stack-queues-da991e581b1b4be38b8c707eb40395d1?pvs=21) | DFS | Memory(Stack, Heap) |
| [Trees, Tries, Graph](https://www.notion.so/Trees-and-Graphs-3b7060d22bc7449abe493c4250432f8f?pvs=21) | Binary Search | Recursion |
| Heaps | Merge Sort | Dynamic Programing |
| Vectors / ArrayList | Quick sort | Big O & Space |
| Hash tables | | |

## DSA

## ALG

## power of 2

| Power of 2 ($2^n$) | Exact value ($X$) | Approx. Value | Bytes into |
| ------------------ | ----------------- | ------------- | ---------- |
| 7 | 128 | | |
| 8 | 256 | | |
| 10 | 1024 | 1 thousand | 1 KB |
| 16 | 6 5536 | | 64 KB |
| 20 | 104 8576 | 1 million | 1 MB |
| 30 | 10 7374 1824 | 1 billion | 1 GB |
| 32 | 42 9496 7296 | | 4 GB |
| 40 | 1 0995 1162 7776 | 1 trillion | 1 TB |
## 時間複雜度 vs 演算法
- OA通常回限制Python 限制 4sec、C++ 2sec，通常一次可以執行$10^{18}$，因此如果看到題目沒有想法的時候可以用限制反推可能的演算法

| n<=x, x= | O(x), x= | ALG |
| --------- | -------------------- | ----------------------------------------------------------------------------- |
| | $n^k$ | iter subset of size $k$ |
| $10$ | $n!$, $n^7$, $n^6$ | $n!$ (iter all permutation) |
| $20$ | $2^n*n$, $n^5$ | $2^n$ (iter all subsets) |
| $80$ | $n^4$ | |
| $400$ | $n^3$ | $n^3$ (iter subset of size 3, iter triplets) |
| $7500$ | $n^2$ | $n^2$ (quick sort worst) |
| $7*10^4$ | $n*sqrt(n)$ | |
| $5*10^5$ | $nlogn$ | $nlogn$(merge sort, quick sort avg. (worst $n^2$)) |
| $5*10^6$ | $n$ | $n$ (two pointer, sliding window, Union and Find) |
| $10^{18}$ | $1$, $log^n$, $logn$ | $1$ (math), $logn$(BS, sorted set, map, heap per op), $sqrt(n)$(prime number) |

## 單字表
- anagram：指兩個字串的字母相同，但是排列不同，例如：'anagram' 和 'nagaram'。
- Parentheses  括號
- **_diameter_** _of the tree_: The **diameter** of a binary tree is the **length** of the longest path between any two nodes in a tree. This path may or may not pass through the root.

## 競技程式
- uva
-