数据结构_0_概述

参阅算法通关手册LeetCode | 算法通关手册LeetCode数据结构与算法 | 菜鸟教程在网络上留点痕迹记录学习过程。一、数据结构与算法算法 数据结构 程序「算法」是解决问题的方法或步骤「数据结构」则是数据在计算机中的组织方式及其相关操作。「程序」就是算法和数据结构的具体实现。注当前对程序的说明会相对狭义从软件工程的概念来说除去代码外文档工作同样也应当包含的程序的范畴内部需求定义概要设计详细设计编码 等各个阶段的文档都是很重要的。算法也罢数据结构也罢 虽然形式上表现为代码的实现物理实现逻辑对于平台语言的具体代码实现在现今大模型盛行的现实工作环境中学习算法和数据结构或许不能够直接帮助我们在编程时从时间复杂度和空间复杂度等角度优化解决方案提升逻辑思维能力写出高质量的代码。但了解底层实现原理是能让我们在当前时代处理问题的时候更有底气和独立的思考从而不至于人云亦云。数据结构数据结构通常分为逻辑结构和物理结构两大类。逻辑结构描述数据元素之间的关系主要包括集合结构、线性结构、树形结构和图形结构。物理结构指数据在计算机中的实际存储方式主要有顺序存储结构和链式存储结构。逻辑结构强调数据元素之间的相互关系而物理结构则关注这些关系在计算机内的具体实现。例如线性表中的「栈」在逻辑上属于线性结构元素之间是一对一的关系除首尾元素外每个元素有唯一前驱和后继。在物理实现上栈可以采用顺序存储即顺序栈元素在内存中连续存放也可以采用链式存储即链式栈元素在内存中不一定连续通过指针连接算法算法是解决特定问题的有序操作步骤的集合。一个算法应具备以下五个基本特性输入、输出、有穷性、确定性、可行性。优秀的算法通常追求以下目标正确性、可读性、健壮性、更低的时间复杂度运行时间更短和更低的空间复杂度占用内存更小二、时间复杂度算法复杂度Algorithm complexity用于衡量算法在输入规模为 n 时所需的时间和空间资源。问题规模 n指的是算法输入的数据量最佳时间复杂度最理想输入下的时间复杂度最坏时间复杂度最差输入下的时间复杂度平均时间复杂度随机输入下的期望时间复杂度时间复杂度通常记作 T(n)O(f(n))称为渐近时间复杂度Asymptotic Time Complexity用于描述当问题规模 n 趋近于无穷大时算法运行时间的增长趋势。我们常用渐近符号如 O、Ω、Θ 等来表达这种增长关系。渐近时间复杂度只关注主导项忽略常数和低阶项从而简洁地反映算法的本质效率。O用于描述算法运行时间的上限通常反映算法在最坏情况下的性能。Ω用于描述算法运行时间的下界通常反映算法在最优情况下的性能。Θ用于描述算法运行时间的精确数量级即算法在最好和最坏情况下的增长速度都与 f(n) 保持一致。就学习理解而言其上下界代表了和f(n)的增长率的对比相同、不高于、不低于一般关注最坏时间复杂度,计算时间复杂度可以分为以下几个步骤确定基本操作找出算法中执行次数最多的语句通常是最内层循环的核心操作。估算执行次数只关注基本操作的最高阶项忽略常数系数和低阶项。用大 O 符号表示将上一步得到的数量级用 O 符号表示出来。加法原则多个代码块顺序执行时总时间复杂度等于其中最大的那一个。乘法原则循环嵌套时总时间复杂度等于各层复杂度的乘积。时间复杂度没有循环和递归的算法时间复杂度通常为O(1)。单层循环遍历 n 个元素的算法时间复杂度为 O(n)。每次操作将问题规模缩小一半的算法如「二分查找」和「分治算法」时间复杂度为 O(log n)。线性对数一般出现在排序算法中例如「快速排序」、「归并排序」、「堆排序」等时间复杂度为 O(nlogn)。指数时间复杂度 O() 通常出现在每一步都存在两种选择、递归分支成倍增长的算法中如递归斐波那契、子集枚举等时间复杂度为O()。阶乘时间 O(n!) 通常出现在需要枚举所有排列或组合的算法中如全排列、旅行商问题暴力解法等。随着输入规模 n 的增加算法的执行次数以阶乘级别增长计算量极大几乎无法处理较大的输入规模三、空间复杂度空间复杂度Space Complexity在问题的输入规模为 n 的条件下算法所占用的空间大小可以记作为 S(n)。一般将算法的辅助空间作为衡量空间复杂度的标准。空间复杂度的计算主要考虑算法运行过程中额外占用的空间包括局部变量和递归栈空间。四、各复杂度图形化Desmos | 图形计算器