Về Chương 6
Laser Scan: Tìm Kiếm
LASER SCAN
TÌM KIẾM TUYẾN TÍNH vs NHỊ PHÂN
Mảng đã sắp xếp | O(n) vs O(log n)
Tìm:
3
7
11
15
18
21
26
32
35
40
▶ Bắt đầu
🔴 Tìm Kiếm Tuyến Tính — O(n)
3
[0]
7
[1]
11
[2]
15
[3]
18
[4]
21
[5]
26
[6]
32
[7]
35
[8]
40
[9]
Bước hiện tại:
kiểm tra index undefined
🟣 Tìm Kiếm Nhị Phân — O(log n)
3
[0]
7
[1]
11
[2]
15
[3]
18
[4]
21
[5]
26
[6]
32
[7]
35
[8]
40
[9]
🔴 Tuyến Tính
⏱ Thời gian:
O(n)
💾 Bộ nhớ:
O(1)
📋 Điều kiện:
Bất kỳ mảng
🏆 Tốt nhất:
O(1)
🔻 Xấu nhất:
O(n)
🟣 Nhị Phân
⏱ Thời gian:
O(log n)
💾 Bộ nhớ:
O(1)
📋 Điều kiện:
Mảng đã sắp xếp
🏆 Tốt nhất:
O(1)
🔻 Xấu nhất:
O(log n)