做书法网站的目的,企业登记代理公司,中国公司排行榜前十名,创建一个网站的创业计划书目录
一、数据结构是什么
二、算法是什么
三、算法的效率 3.1 复杂度的概念
四、时间复杂度 4.1 大O渐进表示法 4.2 算法题分析
五、空间复杂度 5.1 复杂度对比 5.2 算法题题分析 正文开始
一、数据结构是什么
每个计算机专业的同学在大学都会接触到一门计算机必修课《数…目录
一、数据结构是什么
二、算法是什么
三、算法的效率 3.1 复杂度的概念
四、时间复杂度 4.1 大O渐进表示法 4.2 算法题分析
五、空间复杂度 5.1 复杂度对比 5.2 算法题题分析 正文开始
一、数据结构是什么
每个计算机专业的同学在大学都会接触到一门计算机必修课《数据结构与算法》
在大数据时代我们要将数据存储、组织起来必须得依靠数据结构指相互之间存在一种或多种特定关系的数据元素的集合。没有一种数据结构对所有用途都有用所以我们要学各式各样的数据结构。 二、算法是什么
算法就是定义良好的计算过程。
比如说将一个数组升序排序并输出可以将数组每个元素比较一下看谁小放前面也可以用冒泡排序对数组进行排序或者快速排序等等多种解法你要找到最优的解法就称为最优算法。
对标大厂的岗位算法工程师。 三、算法的效率
有那么多种算法如何衡量一个算法的好坏呢
通过复杂度衡量 3.1 复杂度的概念
算法在编写成可执行程序后运行时需要消耗时间资源和空间内存资源。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量既时间复杂度和空间复杂度。
时间复杂度主要衡量算法的运行快慢程序给出结果要多久而空间复杂度主要衡量一个算法运行所需要的额外空间。经过计算机行业的迅速发展计算机的内存容量已经达到了很高的程度所以我们已经不再特别关注一个算法的空间复杂度。 四、时间复杂度
在数学的学习中求解未知数有一元一次方程ax b 0 、二元一次方程axbyc0.....
在计算机科学中计算算法的时间复杂度用函数式T(N)来表示。时间复杂度用来衡量程序的运行时间效率接下来我用C语言中clock计算一下某个程序的运行时间 以上计算的是两个for循环所需要的时间t1记录开始时间t2记录结束时间两个一减就是for循环所需时间 计算出来的时间是13099毫秒那么13099毫秒就一定是它真实执行时间吗在运行几次看看 可以发现程序每次运行的时间都不一样无法精确给出一个时间只能给出一个差不多的数字所以我们无法通过clock函数计算出程序执行的时间复杂度
1因为程序运行时间和编译环境和运行机器的配置都有关比如同一个算法程序用一个老编译器进行编译和新编译器在同样机器下运行时间不同
2同一个算法程序用一个低配置机器和新高配置机器运行时间不同
3并且时间只能程序写好后测试不能写程序前通过理论思想计算评估程序写完才能用clock函数计算
那么算法的时间复杂度是一个函数式T(N)到底是什么呢
这个函数式计算了程序的执行次数是写程序前通过理论思想计算评估的一个函数式用来表示输入条件N对时间的影响趋势。
上面我已经通过clock给大家演示过无法精确计算出程序的时间那么影响时间复杂度的条件有每条语句的执行时间*每条语句的执行次数。由于无法给出精确时间数据所以每条语句的执行时间即使有差别但是微乎其微我们可以忽略不计认为每条语句的执行时间是相同的上面例子13009毫秒和13144毫秒差别不大忽略不计之间差别
既然每条语句的执行时间忽略不计那么影响时间复杂度的条件为每条语句的执行次数 例如以上代码count0语句只执行了一次count语句在两个for循环内部第一个for循环循环N次第二个for循环也循环N次所以count语句执行了n^2次。用时间复杂度函数式T(N) n^2,其中N表示影响时间复杂度的输入条件N给的值不同循环的次数不同算法的时间复杂度T(N)也就不同
有同学可能会问程序时间复杂度除了count外不是还有个count 0语句的执行次数吗怎么不加上为T(N) n^2 1
实际中我们计算时间复杂度时计算的也不是程序的精准执行次数计算出精准次数意义不大因为我们计算时间复杂度只是想比较算法程序的增长量级也就是输入条件N不断变大时T(N)的差别。T(N) n^21随着N的增大加1对整个程序时间复杂度影响不大它都已经n^2了-1已经影响不大所以忽略不计我们只需要计算程序能代表增长量级的大概执行次数既然是大概的我们通常用大O的渐进表示法。 4.1 大O渐进表示法
用于描述函数渐进行为的数学符号表示算法的复杂度 4.2 算法题分析
案例一 T(N)用来表示输入条件N对时间的影响趋势。
for循环中count的执行次数为2N而while内部count的循环次数为10
T(N) 2N10 根据大O阶规则12N1010去掉规则2常量系数2去掉 案例二 count执行多少次受 k100 影响所以T(N)100根据大O规则3写成O(1)
其中1不是表示程序只执行一次而是用1取代常量 案例三 五、空间复杂度 空间复杂度也是一个数学表达式是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。也使用大O渐进表示法规则与其一样。
注意函数运行时所需的栈空间存储参数、局部变量、一些寄存器信息等在编译期间已经确定好了空间复杂度计算的是函数运行时所需的额外空间。 案例一 BubbleSort的函数栈帧在编译期间就已经分配好了其空间复杂度是计算函数内所额外申请的空间有exchange等有限个局部变量根据大O表示法的规则使⽤常数个额外空间为O(1) 案例二 执行一次Fac函数内部递归调用一次Fac(N-1)*N函数递归的复杂度取决于函数调用的次数Fac函数内部调用了n-1次当N0时不再调用O(n-1)根据大O表示法规则最后为O(n) 5.1 复杂度对比 从以上表格可以看出数据n的数值不断增大不同空间复杂度所占用空间的比较 5.2 算法题分析 此处开辟的是一个二维数组数组有n行每行分别有1,2,3,...n列等差数列计算公式是n(n 1)/2个元素空间根据大O规则空间复杂度为n^2 图解 完
