辽宁工程建设信息网网站,新手学做网站pdf下载,宠物网站 html模板,杭州余杭网站建设文章目录 前言1 数据结构与算法1.1 数据结构1.2 算法 2 算法复杂度2.1 算法复杂度简介2.2 时间复杂度2.3 空间复杂度 3 总结 前言
Datawhale组队学习丨9月Leetcode算法入门与数组丨打卡笔记
这篇博客以及接下来几篇将会是一个 入门型 的文章#xff0c;主要是自己学习的一个… 文章目录 前言1 数据结构与算法1.1 数据结构1.2 算法 2 算法复杂度2.1 算法复杂度简介2.2 时间复杂度2.3 空间复杂度 3 总结 前言
Datawhale组队学习丨9月Leetcode算法入门与数组丨打卡笔记
这篇博客以及接下来几篇将会是一个 入门型 的文章主要是自己学习的一个记录。
内容会参考这篇笔记很详细LeetCode 算法笔记Leetcode-Notes
1 数据结构与算法 程序 算法 数据结构
算法解决问题的方式、方法或者过程。数据结构数据的计算机表示和相应的一组操作。程序由算法和数据结构组成并进行具体实现。
程序设计的所要追求的是
更加合适的数据结构 花费时间更少、占用空间更小的算法。
LeetCode 算法笔记Leetcode-Notes 笔记中写道如果把程序比喻成做菜那么各种食材和调味料就是数据结构而不同的做菜方法或者说不同的烹饪方式就是算法。那么色香味俱全就是做菜的追求程序也是这样通过合适的算法以及合适的数据结构产生一个高质量的代码去解决问题。
1.1 数据结构
数据结构Data Structure带有结构特性的数据元素的集合。简言之就是 数据的组织结构用来组织、存储数据。用来提高计算机硬件的利用效率。
通过学习数据结构我们可以了解和掌握计算中中的数据是以什么样的方式进行组织和存储的。
数据结构的分类方式
1. 逻辑结构
集合结构数据元素同属于一个集合彼此互相独立除此之外无其他关系。 线性结构数据元素之间是一对一关系。也就是线性结构中的数据元素除了首尾元素左右两侧都只有一个数据于其相邻。 数组、链表栈、队列、哈希表都属于线性结构类型。 树形结构数据元素之间是一对多的关系。 图形结构数据元素之间是多对多的关系。 2. 物理结构
顺序存储结构数据元素之间的逻辑关系通过数据元素的存储地址来反映。逻辑上相邻的数据元素在物理地址上相邻。 优点简单、易理解且实际占用最少的存储空间。缺点 需要占用一片地址连续的存储单元并且存储分配要事先进行另外对于一些操作的时间效率较低移动、删除元素等操作。 链式存储结构将数据元素存放在任意的存储单元里存储单元可以连续也可以不连续。 链结点每个元素所占用的若干单元组合。存放当前元素数据信息和下一元素所在链接点的指针。 优点 存储空间不必事先分配在需要存储空间的时候可以临时申请不会造成空间的浪费一些操作的时间效率远比顺序存储结构高插入、移动、删除元素。缺点不仅数据元素本身的数据信息要占用存储空间指针也需要占用存储空间链式存储结构比顺序存储结构的空间开销大。 1.2 算法
算法解决问题的方法或者流程。
它不依赖于任何一种语言可以用 自然语言、编程语言Python、C、C、Java 等 描述也可以用 伪代码、流程图 来表示。
1. 算法的基本特性
输入没有、一个或者多个输入。输出一个或多个参数作为算法的输出。有穷性算法必须在有限的步骤内结束。确定性每条指令必须有明确的含义。可行性每一步都能通过执行有限次数完成。
2. 算法追求的目标
所需运行时间更少时间复杂度更低占用内存空间更小空间复杂度更低。
2 算法复杂度
2.1 算法复杂度简介
算法复杂度Algorithm complexity在问题的输入规模为 n n n 条件下程序的时间使用情况和空间使用情况。
比较算法优劣的两种方法
事后统计计算机执行后对运行时间和空间使用情况的记录并挑选出好的算法。预先估算常用计算机执行前对算法中步骤的时间复杂度和空间复杂度的估算并挑选出好的算法。
问题的输入规模 n n n 算法问题输入的数据量大小。
排序算法中 n n n 表示需要排序的元素数量。查找算法中 n n n 表示查找范围内的元素总数比如数组大小、二维数组矩阵大小、字符串长度、二叉树节点数、图的节点数、图的边界点等。二进制计算相关算法中 n n n 表示二进制的展开宽度。
2.2 时间复杂度
1.时间复杂度简介
时间复杂度Time Complexity在问题的输入规模为 n n n 的条件下算法运行所需要花费的时间可以记作为 T ( n ) T(n) T(n) 。
度量标准基本操作次数。
什么是基本操作
算法执行中的每一条语句。每一次基本操作都可以在常数时间内完成。
2.渐进符号
渐进符号Asymptotic Symbol专门用来刻画函数的增长速度的。简单来说渐进符号只保留了 最高阶幂忽略了一个函数中增长较慢的部分比如 低阶幂、系数、常量。因为当问题规模变的很大时这几部分并不能左右增长趋势所以可以忽略掉。 Θ \Theta Θ 渐进紧确界符号 O O O 渐进上界符号 o o o 非渐近紧确上界符号 Ω \Omega Ω 渐进下界符号 ω \omega ω非渐近紧确下界符号 渐近记号 Θ \Theta Θ、 O O O、 o o o、 Ω \Omega Ω、 ω \omega ω关系
记号含义通俗理解 Θ \Theta Θ紧确界相当于 O O O大欧上界相当于 o o o小欧非紧的上界相当于 Ω \Omega Ω大欧米伽下界相当于 ω \omega ω小欧米伽非紧的下界相当于 3.时间复杂度计算
计算算法的时间复杂度的步骤 确定基本操作首先需要明确算法中的基本操作是什么这些基本操作通常是算法中执行一次所需要的时间最长的操作。 计算每个基本操作的执行次数对于算法中的每个基本操作需要计算它们分别会执行多少次。这通常涉及到对算法中的循环、递归等结构进行分析。 求和并简化将每个基本操作的执行次数加总并进行简化。通常可以根据常见的时间复杂度规则如忽略常数项、保留最高次项等来简化计算。 得出时间复杂度表达式根据求和并简化后的结果得出算法的时间复杂度表达式。常见的时间复杂度包括 O ( 1 ) O(1) O(1)、 O ( n ) O(n) O(n)、 O ( n 2 ) O(n^2) O(n2)、 O ( n ! ) O(n!) O(n!)、 O ( log n ) O(\log n) O(logn)、 O ( n log n ) O(n \log n) O(nlogn)等。
需要注意的是时间复杂度只是对算法的时间性能进行粗略估计它描述的是算法的增长率而非具体的执行时间。在实际应用中还需要考虑输入规模、硬件环境等因素来综合评估算法的效率。
计算时间复杂度时原则 忽略常数项在计算时间复杂度时通常会忽略常数项。因为常数项对于大规模数据来说影响较小而且不同的机器、不同的编译器等因素都会影响常数项。 保留最高次项在计算时间复杂度时通常只保留最高次项因为最高次项对于大规模数据来说影响最大。 乘法法则如果一个算法中有多个嵌套的循环那么它们的时间复杂度应该用乘法法则计算。 加法法则如果一个算法中有多个不同的操作那么它们的时间复杂度应该用加法法则计算。 最坏情况分析在计算时间复杂度时通常会假设算法在最坏情况下的时间复杂度因为最坏情况下的时间复杂度可以保证算法在任何情况下都不会超时。 平均情况分析有些算法的时间复杂度与输入数据的分布情况有关这时需要进行平均情况分析。
总之计算时间复杂度需要遵循科学严谨的原则同时也需要结合具体的算法和应用场景来进行综合评估。
常见的时间复杂度
常数时间复杂度 O ( 1 ) O(1) O(1)无论输入规模大小算法的执行时间都是常数级别的即执行时间固定。
def algorithm(n):a 1b 2res a * b nreturn res对数时间复杂度 O ( log n ) O(\log n) O(logn)算法的执行时间与输入规模的对数成正比常见的例子是二分查找算法。
def algorithm(n):cnt 1while cnt n:cnt * 2return cnt线性时间复杂度 O ( n ) O(n) O(n) 算法的执行时间与输入规模成线性关系即随着输入规模的增加执行时间也相应增加。例如遍历一个数组的算法。
def algorithm(n):sum 0for i in range(n):sum 1return sum线性对数时间复杂度 O ( n log n ) O(n \log n) O(nlogn)算法的执行时间与输入规模的对数乘以输入规模成正比常见的例子是快速排序和归并排序等排序算法。
def algorithm(n):cnt 1res 0while cnt n:cnt * 2for i in range(n):res 1return res平方时间复杂度 O ( n 2 ) O(n^2) O(n2)算法的执行时间与输入规模的平方成正比例如嵌套循环的算法。
def algorithm(n):res 0for i in range(n):for j in range(n):res 1return res最佳、最坏、平均时间复杂度 最佳时间复杂度Best Case Time Complexity指在最理想的情况下算法执行所需的最少时间。最佳时间复杂度表示算法在最有利的输入情况下的性能表现。 最坏时间复杂度Worst Case Time Complexity指在最不利的情况下算法执行所需的最长时间。最坏时间复杂度表示算法在最差的输入情况下的性能表现。 平均时间复杂度Average Case Time Complexity指算法执行所需时间的平均值考虑了所有可能的输入情况下的性能表现。平均时间复杂度需要对输入的概率分布进行分析通常需要使用概率论或统计学的方法来计算。
2.3 空间复杂度
空间复杂度是衡量算法在执行过程中所需的额外空间或内存资源的度量。它描述的是算法所需的额外空间随着输入规模增加而增长的趋势。
通常空间复杂度可以分为以下几种情况 常数空间复杂度 O ( 1 ) O(1) O(1)算法所需的额外空间是固定的与输入规模无关。例如只使用有限个变量的算法。 线性空间复杂度 O ( n ) O(n) O(n)算法所需的额外空间随着输入规模线性增长。例如需要存储输入数据的数组或列表。 平方空间复杂度 O ( n 2 ) O(n^2) O(n2)算法所需的额外空间随着输入规模的平方增长。例如需要存储二维矩阵的算法。 指数空间复杂度 O ( 2 n ) O(2^n) O(2n)算法所需的额外空间随着输入规模的指数增长。例如需要存储所有可能子集的算法。
需要注意的是空间复杂度并不仅仅取决于算法中的变量和数据结构的使用情况还受到函数调用、递归等因素的影响。在实际应用中除了考虑时间复杂度外也需要关注算法的空间复杂度以避免因为内存不足导致程序异常或效率低下。
3 总结 参考文献
[1] https://datawhalechina.github.io/leetcode-notes/#/[2] https://blog.csdn.net/so_geili/article/details/53353593
—— END —— 如果以上内容有任何错误或者不准确的地方欢迎在下面 留言。或者你有更好的想法欢迎一起交流学习~~~
更多精彩内容请前往 AXYZdong的博客
