eclipse网站开发流程图,2020一建试题,合肥网站建设司图,js网站模板下载【数据结构与算法——TypeScript】
算法的复杂度分析
什么是算法复杂度(现实案例)#xff1f;
❤️#x1f525; 前面已经解释了什么是算法#xff1f; 其实就是解决问题的一系列步骤操作、逻辑。 ✅ 对于同一个问题#xff0c;我们往往有很多种解决思路和方法#x…【数据结构与算法——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) ❣️ 我们就说该算法 具有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 StructureAccessSearchInsertionDeletionArrayO(1)O(N)O(N)O(N)Linked ListO(N)O(N)O(1)O(1) 数组是一种连续的存储结构通过下标可以直接访问数组中的任意元素。 时间复杂度 对于数组随机访问时间复杂度为O(1),插入和删除操作的时间复杂度为O(n)。空间复杂度数组需要连续的存储空间空间复杂度为 O(n) 链表是一种链式存储结构通过指针链接起来的节点组成访问链表中元素需要从头结点开始遍历 **时间复杂度**对于链表随机访问时间复杂度为O(n)插入和删除的时间复杂度为O(1)**空间复杂度**链表需要为每个节点分配存储空间空间复杂度为O(n) 在实际开发中选择使用数组还是链表需要根据具体应用场景来决定 如果数据量不大且需要频繁随机访问元素使用数组可能会更好如果数据量很大或者需要频繁插入和删除元素使用链表可能会更好 【数据结构与算法——TypeScript】系列笔记 1. 【数据结构与算法——TypeScript】数组、栈、队列、链表
