深入理解数据结构和算法从基础到时间复杂度分析一、什么是数据结构数据结构是指存储、组织数据的方式。数据存储的种类有很多比如字符串、整数、浮点数等。同样的数据采用不同的组织方式就形成了不同的数据结构。示例对比列表 vs 字典使用列表存储个人信息p1[水哥,18,男,山西]使用字典存储个人信息p2{name:水哥,age:18,gender:男,address:山西}二、什么是算法算法是为了满足业务需求、实现业务目的而采用的各种方法和思路的集合。算法的独立性算法是独立存在的一种解决问题的方法和思想。对于算法来说实现的语言并不重要重要的是思想。同一个算法可以用不同的语言实现Python、Java、C等。算法示例求5个2的和方法1乘法res 5 * 2方法2加法res2 2 2 2 2 2三、算法的作用提高代码程序的运行性能面试必备知识时间复杂度和空间复杂度四、穷举法穷举法是对解决问题的所有可能情况一个不漏地进行检验将问题的所有可能性依次过一遍。案例求解abc1000且a²b²c²方法1三重循环穷举forainrange(0,1001):forbinrange(0,1001):forcinrange(0,1001):ifa**2b**2c**2andabc1000:print(a,b,c)算法的五大特性有输入 算法具有0个或多个输入有输出 算法至少有1个或多个输出有穷性 算法在有限的步骤之后会自动结束不会无限循环确定性 算法中的每一步都具有确定的含义不会出现二义性可行性 算法的每一步都是可行的能够执行有限的次数方法2优化循环减少不必要的计算forainrange(0,1001):forbinrange(0,1001):c1000-a-bifa**2b**2c**2:print(a,b,c)五、时间复杂度时间复杂度的定义算法的时间复杂度T是关于问题规模n的函数。它表示一个算法随着问题规模不断变化的最主要趋势。代码执行总时间(T) 操作步骤 × 操作步骤执行时间大O记法大O记法用于表示时间复杂度主要关注随问题规模变化而变化的因素忽略次要因素。算法1T(n) n³ × 10 O(n³)算法2T(n) n² × 10 O(n²)时间复杂度的计算规则基本操作时间复杂度为O(1)顺序结构按加法计算循环结构按乘法计算分支结构取最大值只关注最高次项忽略其他次项和常数项默认指最坏时间复杂度时间复杂度示例O(1) - 常数阶sum100200O(1) - 常数阶a 100b 200c 100 200O(n) - 线性阶for i in range(0, n):print(i)O(n²) - 平方阶if condition:# O(n)else:# O(n²)最好、最坏、平均时间复杂度python最好O(1)最坏O(n)def test(l, n, x):pos -1for i in range(0, n):if l[i] x:pos ibreakreturn pos六、常见时间复杂度对比时间复杂度 名称 示例O(1) 常数阶 简单赋值运算O(logn) 对数阶 二分查找O(n) 线性阶 单层循环O(nlogn) 线性对数阶 归并排序O(n²) 平方阶 双重循环O(n³) 立方阶 三重循环大小关系O(1) O(logn) O(n) O(nlogn) O(n²) O(n³)对数阶示例pythonO(logn) - i以二倍速度增长deftest():i1whilein:ii*2七、空间复杂度空间复杂度一个算法在运行过程中临时占用内存存储空间大小的度量。使用 S(n) 表示算法所耗费的存储空间同样使用O()记法。空间复杂度大小关系O(1) O(logn) O(n) O(n²) O(n³)空间复杂度示例python注意此代码存在引用问题演示用list1[]list2[]foriinrange(0,5):forjinrange(0,5):list2.append(j)list1.append(list2)print(list1)总结概念 核心要点数据结构 存储和组织数据的方式算法 解决问题的方法和思路时间复杂度 算法执行时间随问题规模的变化趋势空间复杂度 算法运行时占用的内存空间大小大O记法 用于表示算法复杂度的一种数学记法