天津如何做百度的网站推广,建站哪家好社区,四川网络推广公司哪家好,有没有做代理商的明细网站算法#xff08;Algorithm#xff09;是指用来操作数据、解决程序问题的一组方法。对于同一个问题#xff0c;使用不同的算法#xff0c;也许最终得到的结果是一样的#xff0c;比如排序就有前面的十大经典排序和几种奇葩排序#xff0c;虽然结果相同#xff0c;但在过程…算法Algorithm是指用来操作数据、解决程序问题的一组方法。对于同一个问题使用不同的算法也许最终得到的结果是一样的比如排序就有前面的十大经典排序和几种奇葩排序虽然结果相同但在过程中消耗的资源和时间却会有很大的区别比如快速排序与猴子排序。 那么我们应该如何去衡量不同算法之间的优劣呢 主要还是从算法所占用的「时间」和「空间」两个维度去考量。 时间维度是指执行当前算法所消耗的时间我们通常用「时间复杂度」来描述。 空间维度是指执行当前算法需要占用多少内存空间我们通常用「空间复杂度」来描述。 本小节将从「时间」的维度进行分析。 什么是大O 当看「时间」二字我们肯定可以想到将该算法程序运行一篇通过运行的时间很容易就知道复杂度了。 这种方式可以吗当然可以不过它也有很多弊端。 比如程序员小吴的老式电脑处理10w数据使用冒泡排序要几秒但读者的iMac Pro 可能只需要0.1s这样的结果误差就很大了。更何况有的算法运行时间要很久根本没办法没时间去完整的运行还是比如猴子排序。 那有什么方法可以严谨的进行算法的时间复杂度分析呢 有的! 「 远古 」的程序员大佬们提出了通用的方法「 大O符号表示法 」即 T(n) O(f(n))。 其中 n 表示数据规模 O(f(n))表示运行算法所需要执行的指令数和f(n)成正比。 上面公式中用到的 Landau符号是由德国数论学家保罗·巴赫曼Paul Bachmann在其1892年的著作《解析数论》首先引入由另一位德国数论学家艾德蒙·朗道Edmund Landau推广。Landau符号的作用在于用简单的函数来描述复杂函数行为给出一个上或下确界。在计算算法复杂度时一般只用到大O符号Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O最初是用大写希腊字母但现在都用大写英语字母O小o符号也是用小写英语字母oΘ符号则维持大写希腊字母Θ。 注本文用到的算法中的界限指的是最低的上界。 常见的时间复杂度量级 我们先从常见的时间复杂度量级进行大O的理解 常数阶O(1) 线性阶O(n) 平方阶O(n²) 对数阶O(logn) 线性对数阶O(nlogn) O(1) 无论代码执行了多少行其他区域不会影响到操作这个代码的时间复杂度都是O(1) 1void swapTwoInts(int a, int b){2 int temp a;3 a b;4 b temp;5} O(n) 在下面这段代码for循环里面的代码会执行 n 遍因此它消耗的时间是随着 n 的变化而变化的因此可以用O(n)来表示它的时间复杂度。 1int sum ( int n ){2 int ret 0;3 for ( int i 0 ; i n ; i ){4 ret i;5 }6 return ret;7} 特别一提的是 c * O(n) 中的 c 可能小于 1 比如下面这段代码 1void reverse ( string s ) {2 int n s.size();3 for (int i 0 ; i n/2 ; i){4 swap ( s[i] , s[n-1-i]);5 }6} O(n²) 当存在双重循环的时候即把 O(n) 的代码再嵌套循环一遍它的时间复杂度就是 O(n²) 了。 1void selectionSort(int arr[],int n){ 2 for(int i 0; i n ; i){ 3 int minIndex i; 4 for (int j i 1; j n ; j ) 5 if (arr[j] arr[minIndex]) 6 minIndex j; 7 8 swap ( arr[i], arr[minIndex]); 9 }10} 这里简单的推导一下 当 i 0 时第二重循环需要运行 (n - 1) 次当 i 1 时第二重循环需要运行 (n - 2) 次。。。。。。不难得到公式 1(n - 1) (n - 2) (n - 3) ... 02 (0 n - 1) * n / 23 O (n ^2) 当然并不是所有的双重循环都是 O(n²)比如下面这段输出 30n 次 Hello,五分钟学算法的代码。 1void printInformation (int n ){2 for (int i 1 ; i n ; i)3 for (int j 1 ; j 30 ; j )4 cout Hello,五分钟学算法 endl;5} O(logn) 1int binarySearch( int arr[], int n , int target){ 2 int l 0, r n - 1; 3 while ( l r) { 4 int mid l (r - l) / 2; 5 if (arr[mid] target) return mid; 6 if (arr[mid] target ) r mid - 1; 7 else l mid 1; 8 } 9 return -1;10} 在二分查找法的代码中通过while循环成 2 倍数的缩减搜索范围也就是说需要经过 log2^n 次即可跳出循环。 同样的还有下面两段代码也是 O(logn) 级别的时间复杂度。 1 // 整形转成字符串 2 string intToString ( int num ){ 3 string s ; 4 // n 经过几次“除以10”的操作后等于0 5 while (num ){ 6 s 0 num%10; 7 num / 10; 8 } 9 reverse(s)10 return s;11 } 1void hello (int n ) {2 // n 除以几次 2 到 13 for ( int sz 1; sz n ; sz sz) 4 for (int i 1; i n; i)5 cout Hello,五分钟学算法 endl;6} O(nlogn) 将时间复杂度为O(logn)的代码循环N遍的话那么它的时间复杂度就是 n * O(logn)也就是了O(nlogn)。 1void hello (){2 for( m 1 ; m n ; m){3 i 1;4 while( i n ){5 i i * 2;6 }7 }8} 更多复杂度分析内容可以在公众号 五分钟学算法 获取转载于:https://www.cnblogs.com/fivestudy/p/10113337.html
