Cirry's Blog

《算法图解》是一本科普读物

2024-02-02
阅读
最后更新:2024-03-29
4分钟
715字

看完了这本书之后,我更觉得《算法图解》是一本算法科普书。

如果你想学习算法,这本书是不适合的,如果你只想了解一下算法,这本书是不错的。

前面部分介绍了一些简单的算法知识,后面说了一些复杂的算法和有趣的问题,供读者自己去深入研究算法问题。

二分法查找

  • 二分法查找是利用了有序数组的特点,通过比较元素的大小,减少查找的次数。
  • 二分法查找的复杂度为 \( O(log_2 n) \)。

js实现:

1
function binarySearch(arr, target) {
2
let low = 0;
3
let high = arr.length - 1;
4
5
while (low <= high) {
6
let mid = Math.floor((low + high) / 2);
7
let guess = arr[mid];
8
9
if (guess === target) {
10
return mid; // 找到目标值,返回索引
11
} else if (guess < target) {
12
low = mid + 1; // 目标值在右侧
13
} else {
14
high = mid - 1; // 目标值在左侧
15
}
16 collapsed lines
16
}
17
18
return -1; // 未找到目标值
19
}
20
21
// 示例
22
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
23
const targetValue = 6;
24
25
const result = binarySearch(sortedArray, targetValue);
26
27
if (result !== -1) {
28
console.log(`目标值 ${targetValue} 在数组中的索引是: ${result}`);
29
} else {
30
console.log(`未找到目标值 ${targetValue}`);
31
}

选择排序

1
function selectionSort(arr) {
2
const n = arr.length;
3
4
for (let i = 0; i < n - 1; i++) {
5
// 假设当前位置的元素是最小的
6
let minIndex = i;
7
8
// 在未排序部分找到最小元素的索引
9
for (let j = i + 1; j < n; j++) {
10
if (arr[j] < arr[minIndex]) {
11
minIndex = j;
12
}
13
}
14
15
// 将最小元素与当前位置交换
12 collapsed lines
16
if (minIndex !== i) {
17
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
18
}
19
}
20
21
return arr;
22
}
23
24
// 示例用法
25
const unsortedArray = [64, 25, 12, 22, 11];
26
const sortedArray = selectionSort(unsortedArray.slice());
27
console.log(sortedArray); // 输出 [11, 12, 22, 25, 64]

快速排序

1
function quickSort(arr) {
2
if (arr.length <= 1) {
3
return arr; // 数组已经有序
4
}
5
6
const pivot = arr[0]; // 选择第一个元素作为基准
7
const left = [];
8
const right = [];
9
10
for (let i = 1; i < arr.length; i++) {
11
if (arr[i] < pivot) {
12
left.push(arr[i]);
13
} else {
14
right.push(arr[i]);
15
}
10 collapsed lines
16
}
17
18
// 递归排序左右子数组,然后合并
19
return quickSort(left).concat(pivot, quickSort(right));
20
}
21
22
// 示例用法
23
const unsortedArray = [64, 25, 12, 22, 11];
24
const sortedArray = quickSort(unsortedArray.slice());
25
console.log(sortedArray); // 输出 [11, 12, 22, 25, 64]

递归

1
// 计算阶乘的递归函数
2
function factorial(n) {
3
// 基本情况:当 n 为 0 或 1 时,阶乘为 1
4
if (n === 0 || n === 1) {
5
return 1;
6
} else {
7
// 递归情况:n 的阶乘等于 n 乘以 (n-1) 的阶乘
8
return n * factorial(n - 1);
9
}
10
}
11
12
// 示例用法
13
const result = factorial(5);
14
console.log(result); // 输出 120

五种常见的时间复杂度

由快到慢排序:

  • \(O(log_n)\)
  • \(O(n)\)
  • \(O(n*log_n)\)
  • \(O(n^2)\)
  • \(O(n!)\)

补充:

  • \( log_2 n \)代表中多少个2相乘等于n。

问题:

  • js中关于数组、栈、队列、散列表的实现
  • 如果你对数据库或高级数据结构感兴趣,请研究如下数据结构:B树,红黑树,堆,伸展树。
本文标题:《算法图解》是一本科普读物
文章作者:Cirry
发布时间:2024-02-02
版权声明:本作品采用「署名-非商业性使用-相同方式共享 4.0 国际」许可协议进行许可。
感谢大佬送来的咖啡☕
alipayQRCode
wechatQRCode