κ°λ°/π€ μκ³ λ¦¬μ¦
μκ³ λ¦¬μ¦ κ°λ . μλ£κ΅¬μ‘°μμμ νκ· ~ μ΅μ μκ° λ³΅μ‘λ
ttoance
2023. 6. 10. 17:56
| μ κ·Ό | νμ | μ½μ | μμ | |
| λ°°μ΄ (array) | O(1) ~ O(1) | O(n) ~ O(n) | O(n) ~ O(n) | O(n) ~ O(n) |
| μ€ν (stack) | O(n) ~ O(n) | O(n) ~ O(n) | O(1) ~ O(1) | O(1) ~ O(1) |
| ν (queue) | O(n) ~ O(n) | O(n) ~ O(n) | O(1) ~ O(1) | O(1) ~ O(1) |
| μ΄μ€ μ°κ²° 리μ€νΈ (doubly linked list) | O(n) ~ O(n) | O(n) ~ O(n) | O(1) ~ O(1) | O(1) ~ O(1) |
| ν΄μ ν μ΄λΈ (hash tablee) | O(1) ~ O(n) | O(1) ~ O(n) | O(1) ~ O(n) | O(1) ~ O(n) |
| μ΄μ§ νμ νΈλ¦¬ (BST) | O(logn) ~ O(n) | O(logn) ~ O(n) | O(logn) ~ O(n) | O(logn) ~ O(n) |
| AVL νΈλ¦¬ | O(logn) ~ O(logn) | O(logn) ~ O(logn) | O(logn) ~ O(logn) | O(logn) ~ O(logn) |
| λ λ λΈλ νΈλ¦¬ | O(logn) ~ O(logn) | O(logn) ~ O(logn) | O(logn) ~ O(logn) | O(logn) ~ O(logn) |
* AVL νΈλ¦¬ : μκ° κ· ν μ΄μ§ νμ νΈλ¦¬λ‘ λ μμ μλΈνΈλ¦¬μ λμ΄λ νμ μ΅λ 1λ§νΌ μ°¨μ΄ λλ€λ νΉμ§μ΄ μμ
* μ΄μ§ νμ νΈλ¦¬ λ Έλμ μ€λ₯Έμͺ½ νμ νΈλ¦¬μλ 'λ Έλ κ°λ³΄λ€ ν° κ°'μ΄ μλ λ Έλλ§ ν¬ν¨λκ³ , μΌμͺ½ νμ νΈλ¦¬μλ 'λ Έλ κ°λ³΄λ€ μμ κ°'μ΄ λ€μ΄μλ νΈλ¦¬
λ°μν