? 1. 时间频度:一个算法花费的时間与算法中语句的执行次数成正比例哪个算法中语句执行的次数多,它花费的时间就多一个算法中语句执行次数被称为语句频度或时間频度T(n)。
-
忽略常数项:如时间频度为T(n) = 2n+20和频度为T(n) = 2n当n越来越大是,两者的结果无限接近故常数项可以忽略;
-
忽略低次项:如时间频度為T(n) = 2n^2+3n+10与T(n) = 2n^2,当n越来越大时两者的结果无限接近。故低次项可以省略;
-
忽略系数:如时间频度为T(n) = 3n^2+20n与T(n) = 5n^2+7n当n越来越大时,两者的结果无限接近故低次项可以省略;
-
一般情况下,算法中的基本操作语句的重复执行次数是问题规模n的某个函数用T(n)表示,若有某个辅助函数f(n)使得当n趋近於无穷大的时候,T(n)/f(n)的极限值为不等于0的常数则称f(n)是T(n)的同数量级函数。记作T(n)= O(f(n)),称O(f(n))为算法的渐进时间复杂度简称时间复杂度。
-
计算時间复杂度的方法:
-
用常数1代替运行时间中的所有加法常数;
-
修改后的运行次数函数中只保留最高阶项;
-
由图可见,我们应该尽可能避免使用指数阶的算法
- 常数阶O(1):无论代码执行了多少行,只要是没有循环等复杂结构那这个代码的时间复杂度就是O(1)。
? 在while循环中假设循环x次之后退出循环,此时2的x次方等于n即x = log2n,也就是说循环log2n次之后代码就结束了因此代码的时间复杂度为O(log2n)。2随着代码的改变而改变i = i *3 时,复杂度为O(log3n).
? 这段代码中for循环里面的代码会执行n遍因此它消耗的时间是随着n变化而变化,因此这类代码都可以用O(n)来表示它的时间复杂度
? 线性对数阶就是指将时间复杂度为O(logn)的代码循环n遍的话,那么它的时间复杂度就是n*O(logN),也就是O(nlogN)
? 把O(n)的代码再循环嵌套循环一遍,它的时间複杂度就变成了O(n2)如果把其中一层循环的n改成m,那么时间复杂度就成了O(nm)
? 原理:相邻两元素相比较,大的往后放每一轮结束时最大的數都会被放到最后面。之后每一轮的比较都可以不用再去比之前排好的最大的数了因此每一轮比较的次数是递减的。
? 原理:从起始索引处开始依次与后面索引的元素进行比较,每一轮都将最小的元素放到起始索引处的位置最后结束时完成排序。
? 对于一个有序数组我们查找一个元素时可以每一次都查中间的那个元素,这样比较大小就能减少一半的元素