【数据结构与算法——TypeScript】
算法的复杂度分析
什么是算法复杂度(现实案例)?
❤️🔥 前面已经解释了什么是算法? 其实就是解决问题的一系列步骤操作、逻辑。
✅ 对于同一个问题,我们往往有很多种解决思路和方法,也就是可以采用不同的算法。
-
举个例子(现实例子):在一个庞大的图书馆中,我们需要找一本书
- 在图书已经按照某种方式摆好的情况下(数据结构是固定的)
-
方式一:顺序查找
- 一本一本找,直到找到想要的书;
-
方式二:先分类找,分类中找这本书
- 先找到分类,在分类中再顺序或某种方式查找
-
方式三:找到检索电脑,查找书的位置,直到找到
- 图书馆通常有自己的图书管理系统
- 利用图书管理系统先找到书的位置,再直接过去找到
什么是算法复杂度(程序案例)?
🖥 在具体一个程序中的案例:让我们用两种不同算法查找数组中(数组有序)给定元素的复杂度
- ✅ 方式一:顺序查找
- 这种算法 从头到尾遍历整个数组,依次比较每个元素和给定元素的值
- 如果 找到相等的元素,则返回下标;如果 遍历完整个数组都没找到,则返回 -1。
/**
- 顺序查找
- @param array 查找的数组
- @param 查找的元素
- @returns 查找到的索引,未找到返回-1
*/
function sequentSearch(array: number[], num: number) {
for (let i = 0; i < array.length; i++) {
const element = array[i];
if (element === num) return i;
}
return -1;
}
const index = sequentSearch([1, 3, 5, 10, 100, 222, 333, 334, 555, 556], 222);
console.log(index);
-
✅ 方式二:二分查找
- 这种算法假设数组是有序的,每次 选择数组中间的元素与给定元素进行比较。
- 如果 相等,则返回下标;如果 给定元素比中间元素小,则在数组的左半部分继续查找;
- 如果 给定元素比中间大,则在数组的右半部分继续查找;
- 这样 每次查找都会将查找范围减半,直到找到想等的元素或者查找范围为空。
function binarySearch(array: number[], num: number) { // 1. 定义左右索引 let left = 0; let right = array.length - 1; // 2.开始查找 while (left <= right) { let mid = Math.floor((left + right) / 2); const midNum = array[mid]; if (midNum === num) { return mid; } else if (midNum < num) { left = mid + 1; } else { right = mid - 1; } } return -1; } const index = binarySearch([1, 3, 5, 10, 100, 222, 333, 334, 555, 556], 222); console.log(index); export {};
测试顺序查找和二分查找的代码
- 使用🔧工具:
npm install hy-algokit
import sequentSearch from './01_查找算法-顺序查找';
import binarySearch from './02_查找算法-二分查找';
import { testOrderSearchEfficiency } from 'hy-algokit';
testOrderSearchEfficiency(sequentSearch);
testOrderSearchEfficiency(binarySearch);
-
❤️🔥 顺序查找算法的时间复杂度是
O(n)
-
❤️🔥 二分查找算法的时间复杂度是
O(log n)
大O表示法(Big O notation)
- 大O表示法(Big O notation)英文翻译为大O符号,中文通常翻译为大O表示法(标记法)。
- 大O符号在分析 算法效率的时候非常有用。
- 🌰 举例:解决 **一个规模为n的问题所花费的时间(或需要步骤的数目)可以表示为:
T(n)= 4n⌃2^ - 2n + 2
**- 当
n
增大 时,n^2^
项开始 占据主导地位,其他各项可以被忽略。
- 🌰 : 当
n = 500
-
✓ 4n2 项是 2n 项的 1000倍大,因此在大多数场合下, 省略后者对表达式的值的影响将是乐意忽略不计的。
-
进一步,如果我们与任一其他级的表达式比较, n2的系数也是无关紧要的的。
-
这样,针对第一个例子, T(n)= 4 n2 - 2n + 2,大O符号就记下剩余的部分,写作:
-
T(n) ∈ O(n2)
或者
-
T(n) = O(n2)
-
-
- 🌰 举例:解决 **一个规模为n的问题所花费的时间(或需要步骤的数目)可以表示为:
- ❣️ 我们就说该算法 具有n2 阶(平方阶)的时间复杂度,表示为O(n2)。
常见的对数阶
- 常用的函数阶
符号 | 名称 |
---|---|
O(1) | 常数(阶、下同) |
O(log n) | 对数 |
O(n) | 线性、次线性 |
O(n log n) | 线性对数、或者对数线性、拟线性、超线性 |
O(n2) | 平方 |
O(n2) , Interger(c > 1) | 多项式,有时叫作‘代数’(阶) |
O(cn) | 指数,有时叫作“几何”(阶) |
空间复杂度
-
空间复杂度指的是,程序运行过程中所需要的额外存储空间。
- 空间复杂度 也可以用大O表示法来表示;
- **空间复杂度的计算方法与时间复杂度类似,**通常需要分析程序中 需要额外分配的内存空间,如数组、变量、对象、递归调用等。
-
🌰 :举例
- 对于一个简单的 递归算法来说,每次调用会在内存中分配新的栈帧,这些栈帧占用了额外的空间。
- 因此,该算法的空间复杂度是 O(n),其中n是递归深度
- 而对于 迭代算法来说,在 **每次迭代中不需要分配额外的空间,**因此 其空间复杂度为O(1)
- 对于一个简单的 递归算法来说,每次调用会在内存中分配新的栈帧,这些栈帧占用了额外的空间。
-
当空间复杂度很大时,可能会导致内存不足,程序崩溃。
-
在平时进行算法优化时,我们通常会进行如下考虑:
- 使用尽量少的空间(优化空间复杂度)
- 使用尽量少的时间(优化时间复杂度)
- 特定情况下:使用 空间换时间或使用 时间换空间。
数组和链表的对比
- 使用大O表示法来对比一下数组和链表的时间复杂度(增删改查)
Data Structure | Access | Search | Insertion | Deletion |
---|---|---|---|---|
Array | O(1) | O(N) | O(N) | O(N) |
Linked List | O(N) | O(N) | O(1) | O(1) |
-
数组是一种连续的存储结构,通过下标可以直接访问数组中的任意元素。
- 时间复杂度: 对于数组,随机访问时间复杂度为O(1),插入和删除操作的时间复杂度为O(n)。
- 空间复杂度:数组需要连续的存储空间,空间复杂度为 O(n)
-
链表,是一种链式存储结构,通过指针链接起来的节点组成,访问链表中元素需要从头结点开始遍历
- **时间复杂度:**对于链表,随机访问时间复杂度为O(n),插入和删除的时间复杂度为O(1)
- **空间复杂度:**链表需要为每个节点分配存储空间,空间复杂度为O(n)
-
💖 在实际开发中,选择使用数组还是链表需要根据具体应用场景来决定
- 如果数据量不大,且需要频繁随机访问元素,使用数组可能会更好
- 如果数据量很大,或者需要频繁插入和删除元素,使用链表可能会更好
【数据结构与算法——TypeScript】系列笔记:
1. 【数据结构与算法——TypeScript】数组、栈、队列、链表