快速html5网页设计的网站,网站策划方案范文,国内wordpress主题免费,上海公司车辆怎么查询违章一.数据结构前言 1.1 数据结构的概念 数据结构(Data Structure)是计算机存储、组织数据的⽅式#xff0c;指相互之间存在⼀种或多种特定关系的数 据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤#xff0c;所以我们要学各式各样的数据结构#xff0c; 如#xff1a…一.数据结构前言 1.1 数据结构的概念 数据结构(Data Structure)是计算机存储、组织数据的⽅式指相互之间存在⼀种或多种特定关系的数 据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤所以我们要学各式各样的数据结构 如线性表、树、图、哈希等
1.2 算法 算法(Algorithm):就是定义良好的计算过程他取⼀个或⼀组的值为输⼊并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤⽤来将输⼊数据转化成输出结果
二.时间复杂度
2.1 复杂度的概念 算法在编写成可执⾏程序后运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好 坏⼀般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度 时间复杂度主要衡量 ⼀个算法的运⾏快慢 ⽽空间复杂度主要衡量 ⼀个算法运⾏所需要的额外空 间 。在计算机发展的早期计算机的存储容量很⼩。所以对空间复杂度非常在乎。但是经过计算机⾏业的迅速发展计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法 的空间复杂度 2.2 时间复杂度的定义 在计算机科学中算法的时间复杂度是⼀个函数式T(N)它定量描述了该算法的运⾏时间实际上时间复杂度的本质是随着输入规模的不断增大算法运行速度的变化趋势时间复杂度是描述程序的时间效率那么为什么不去计算程序的运行时间那 1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系⽐如同⼀个算法程序⽤⼀个⽼编译器进⾏编译和新编译器编译在同样机器下运⾏时间不同。 2. 同⼀个算法程序⽤⼀个⽼低配置机器和新⾼配置机器运⾏时间也不同。 3. 并且时间只能程序写好后测试不能写程序前通过理论思想计算评估 3.3 大O渐进表示法计算的 那么函数式 T (N) 到底是什么呢因为算法的运行时间和基本语句执行次数成正比精确计算执行次数很麻烦且不同程序代码编译出的指令条数不同精确计算意义不大所以我们引入大 O 渐进法它会去掉影响较小的项。下面具体描述大 O 渐进表示法的计算过程 我在简略总结一下 常数归一将运行时间中的加法常数用 1 取代。 保留高阶仅保留运行次数函数中的最高阶项。 去除系数若最高阶项系数不为 1去除该系数。
三.时间复杂度计算案例
3.1 示例1 T(N) MN 由于题目并没有说明M和N的具体大小所以我们不能去掉其中的任意一项 时间复杂度O(MN)
3.2 示例2 T(N) 2*N 10 先将 10 变成 1由于 10 为低阶项去掉 10 高阶项的系数不是1将系数变为1 时间复杂度O(N) 看到这我估计有人会想为啥要去掉系数那×2不是变化挺大的吗那你想一想如果输入规模趋于无穷大那么给他×多少不是一样的吗
3.3 示例3 T(n) 100 如果算法的基本操作执行次数是一个与输入规模无关的常数那么其时间复杂度记为 O(1) 时间复杂度O1表示算法的基本执行次数和输入规模无关
3.4 示例4 1若要查找的字符在字符串第⼀个位置则 T (N) 1 2若要查找的字符在字符串最后的⼀个位置 则 T (N) N 3若要查找的字符在字符串中间位置则 T (N) 2 / N 因此strchr的时间复杂度分为 最好情况 O ( 1 ) 最坏情况 O ( N ) 平均情况 O ( N / 2 ) 为啥关注算法的最坏情况你可以这样理解某一天你和女朋友约好下班后去约会看晚上 20:00 的电影但是你手头有一项工作要完成这项工作的任务量和难度是不确定的所以你也不知道具体几点能结束工作出发去赴约。
现在你有三个时间点可以告诉她你大概能结束工作出发分别是 17:00、18:00、19:00。考虑到工作可能出现各种意外状况比如遇到复杂问题需要花费更多时间解决、中途可能有新的任务插入等为了避免让女朋友等待保证不会耽误看电影你肯定会选择告诉她最晚的那个时间点 19:00。
这就如同在算法中最坏情况代表着在任意输入规模下算法运行的最大次数上界。我们关注最坏情况是因为它能让我们在设计和评估算法时知晓算法在最糟糕场景下的性能表现确保算法在任何情况下都能满足一定的性能要求就像告诉女朋友最晚时间能保证约会按时进行一样
3.5 示例5 若数组有序只需要遍历一遍数组所以他的时间复杂度是O(N)
若数组有序且是降序那么他要比较n-1趟第一次比较n-1次 第二次比较n-2次 以此类推 到1次
所以他是一个等差数列用等差数列求和公式计算是 : 首项是1 尾项是n-1 公差是1 一共有n-1项 用大O计算法进行表示ON^2
3.6 示例6 3.7 示例7 我看过不少面经都对时间复杂度的计算进行了考察这没有捷径多练多算加油吧
