查看网站是否备案,成都 网站开发,中铁二局深圳公司官网,微信无法分享wordpress1.数据结构和算法
#xff08;1#xff09;数据结构是计算机存储、组织数据的方式#xff0c;指相互之间存在⼀种或多种特定关系的数据元素的集合
#xff08;2#xff09;算法就是定义良好的计算过程#xff0c;取一个或一组的值为输入#xff0c;并产生出一个或一组…1.数据结构和算法
1数据结构是计算机存储、组织数据的方式指相互之间存在⼀种或多种特定关系的数据元素的集合
2算法就是定义良好的计算过程取一个或一组的值为输入并产生出一个或一组值作为输出简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果
3算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。时间复杂度主要衡量⼀个算法的运行快慢而空间复杂度主要衡量⼀个算法运行所需要的额外空间
2.时间复杂度
1概念
在计算机科学中算法的时间复杂度是⼀个函数式T(N)它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率
为什么不去计算程序的运行时间
·程序运行时间与编译环境、运行机器的配置有关同一个算法程序用一个老编译器进行编译和用新编译器编译在同样机器下运行时间不同
·同⼀个算法程序用⼀个老低配置机器和新高配置机器运行时间也不同
·运行时间只能程序写好后测试不能在程序写前通过理论思想计算评估
计算时间复杂度计算的不是程序的精确执行次数精确执行次数计算起来很复杂计算时间复杂度只是想比较算法程序的增长量级也就是当N不断变大时T(N)的差别只需要计算程序能代表增长量级的大概执行次数复杂度的表示通常使用大O的渐进表示法
2大O的渐进表示法
大O符号是用于描述函数渐进行为的数学符号
规则
·时间复杂度函数式T(N)中只保留最高阶项去掉低阶项因为当N不断变大时低阶项对结果影响越来越小当N无穷大时就可以忽略不计了
·如果最高阶项存在且不是1则去除这个项目的常数系数因为当N不断变大这个系数对结果影响越来越小当N无穷大时就可以忽略不计了
·T(N)中如果没有N相关的项目只有常数项则用常数1取代常数
3实例
例1计算Fucn1的时间复杂度 T(N)N^22*N10只保留最高次项则时间复杂度为O(N)
例2计算Fucn2的时间复杂度 T(N)2N10只保留最高次项系数改为1则时间复杂度为O(N) 例3计算Fucn3的时间复杂度 T(N)MN若M和N相差不大T(N)可看成2N或2M若MNT(N)M若MNT(N)N故时间复杂度为O(N) 例4计算Fucn4的时间复杂度 T(N)100只有常数项用1代替常数则时间复杂度为O(1) 例5计算Fucn5的时间复杂度 若要查找的字符在字符串第一个位置T(N)1若要查找的字符在字符串最后一个位置T(N)N若要查找的字符在字符串中间位置T(N)N/2或N/21N是偶数或T(N)N1/2N是奇数因此Fucn5的时间复杂度分为最好情况O(1)最坏情况O(N)平均情况O(N)
补充
有些算法的时间复杂度存在最好、平均和最坏情况
最坏情况任意输入规模的最大运行次数(上界)
平均情况任意输入规模的期望运行次数
最好情况任意输入规模的最小运行次数(下界)
大O的渐进表示法在实际中一般情况关注的是算法的上界也就是最坏运行情况
故例5的时间复杂度取O(N) 例6计算BubbleSort的时间复杂度 若数组有序则T(N)N若数组有序且为降序则T (N) N(N-1)/2故BubbleSort的时间复杂度取最差情况为O(N^2) 例7计算Func6的时间复杂度 当n2时执行次数为1当n4时执行次数为2当n16时执行次数为4假设执行次数为x 则2^x n 因此执行次数x log (2) n故Func6的时间复杂度为O(log (2) n)当n接近无穷大时底数的大小对结果影响不大因此一般情况下不管底数是多少都可以省略不写即可以表示为log n建议使用log n
例8计算Fac的时间复杂度 递归算法的时间复杂度单次递归的时间复杂度*递归次数
单次递归的时间复杂度为O(1)递归次数为N故Fac的时间复杂度为O(N)
