镇江网站制作案例,百度收录软件,平面设计公司排名前十,做网站linux和win时间和空间复杂度 1. 算法效率2. 时间复杂度2.1 时间复杂度的概念2.2 大O的渐进表示法2.3 推导大O阶方法2.4 常见时间复杂度计算举例例1例2例3例4 计算 bubbleSort的时间复杂度例5 计算binarySearch的时间复杂度#xff1f;例6 计算阶乘递归factorial的时间复杂度#xff1f;… 时间和空间复杂度 1. 算法效率2. 时间复杂度2.1 时间复杂度的概念2.2 大O的渐进表示法2.3 推导大O阶方法2.4 常见时间复杂度计算举例例1例2例3例4 计算 bubbleSort的时间复杂度例5 计算binarySearch的时间复杂度例6 计算阶乘递归factorial的时间复杂度例7 计算斐波那契递归fibonacci的时间复杂度 3. 空间复杂度例1 计算bubbleSort的空间复杂度例2 计算fibonacci的空间复杂度例3 计算阶乘递归Factorial的空间复杂度 4. 总结 1. 算法效率
算法效率分为两种第一种是时间效率第二种是空间效率。时间效率被称为时间复杂度而空间效率被称作空间复杂度。时间复杂度主要衡量的是一个算法的运行速度而空间复杂度主要衡量一个算法所需要的额外空间在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
2. 时间复杂度
2.1 时间复杂度的概念
时间复杂度的定义在计算机科学中算法的时间复杂度是一个数学函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度即一个算法的运行时间和这个算法当中的语句执行次数有关系语句执行次数越多运行时间就多成正比的一个关系。
2.2 大O的渐进表示法 // 请计算一下func1基本操作执行了多少次//F(N) n^2 2n 10 O(n^2)void func1(int N) {int count 0;for (int i 0; i N; i) {for (int j 0; j N; j) {count; //nnn...n 即n*nn^2}}for (int k 0; k 2 * N; k) {count; //2n}int M 10;while ((M--) 0) {count; //10}System.out.println(count);}Func1执行的基本操作次数 F(N) N^2 2*N 10 实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。 大O符号Big O notation是用于描述函数渐进行为的数学符号
2.3 推导大O阶方法
1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 使用大O的渐进表示法以后即随着N越来越大时 10和2*n会很小可以省略Func1的时间复杂度为O(N^2) 通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。 另外有些算法的时间复杂度存在最好、平均和最坏情况 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界) 例如在一个长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到 在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N)
2.4 常见时间复杂度计算举例
时间复杂度的计算需要配合逻辑来看的
例1 // 计算func2的时间复杂度//F(N) 2n 10 O(N)nvoid func2(int N) {int count 0;for (int k 0; k 2 * N ; k) {count; // 2n}int M 10;while ((M--) 0) {count; //10}System.out.println(count);}例2 // 计算func3的时间复杂度// nm O(nm)void func3(int N, int M) {int count 0;for (int k 0; k M; k) {count; //m}for (int k 0; k N ; k) {count; //n}System.out.println(count);}例3 // 计算func4的时间复杂度// O(1)void func4(int N) {int count 0;for (int k 0; k 100; k) {count; // 100}System.out.println(count);}例4 计算 bubbleSort的时间复杂度
O(n^2而在最好情况下就是原本就是已经排好的顺序O(n) // 计算bubbleSort的时间复杂度//F(N)(1n-1)*(n-1)/2 1/2*n^2 - 1/2*n n^2 即O(n^2)void bubbleSort(int[] array) {for (int end array.length; end 0; end--) { //Nboolean sorted true;for (int i 1; i end; i) { // n-1 n-2 ..21//即当end的值不一样 执行的次数也不一样 (1n-1)*(n-1)/2if (array[i - 1] array[i]) {Swap(array, i - 1, i);sorted false;}}if (sorted true) {break;}}}private void Swap(int[] array, int i, int i1) {}例5 计算binarySearch的时间复杂度
二分查找 一次砍一半 -- n n/2 n/4 … 1 即n/2^x1 -- n2^x 即log2^n O(log2^n) // 计算binarySearch的时间复杂度// 二分查找 一次砍一半 -- n n/2 n/4 ... 1 即n/2^x1 -- n2^x 即log2^n// O(log2^n)int binarySearch(int[] array, int value) {int begin 0;int end array.length - 1; //n-1while (begin end) {int mid begin ((end-begin) / 2);if (array[mid] value)begin mid 1;else if (array[mid] value)end mid - 1;elsereturn mid;}return -1;}例6 计算阶乘递归factorial的时间复杂度
递归的时间复杂度 递归的次数 * 每次递归后执行的次数 O(n) // 计算阶乘递归factorial的时间复杂度// 递归的时间复杂度 递归的次数 * 每次递归后执行的次数// O(n)long factorial(int N) { // n// 三目运算符不是循环 是一个判断 执行的次数是1return N 2 ? N : factorial(N-1) * N;}例7 计算斐波那契递归fibonacci的时间复杂度
F(N) - F(N-1) F(N-2) - F(N-2) F(N-3) F(N-3) F(N-4)
124...2^(n-1) 2^(n-1)-1 即 O(2^n)O(2^n) // 计算斐波那契递归fibonacci的时间复杂度// F(N) - F(N-1) F(N-2) - F(N-2) F(N-3) F(N-3) F(N-4)// 2^01 2^12 2^24 ... 2^(n-1)// 124...2^(n-1) 2^(n-1)-1 即 O(2^n)int fibonacci(int N) {return N 2 ? N : fibonacci(N-1)fibonacci(N-2);}
3. 空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。
例1 计算bubbleSort的空间复杂度
O(1) // 计算bubbleSort的空间复杂度// 有临时变量 没有申请其它数组 O(1)void bubbleSort(int[] array) {for (int end array.length; end 0; end--) {boolean sorted true;for (int i 1; i end; i) {if (array[i - 1] array[i]) {Swap(array, i - 1, i);sorted false;}}if (sorted true) {break;}}}private void Swap(int[] array, int i, int i1) {}例2 计算fibonacci的空间复杂度 // 计算fibonacci的空间复杂度// 动态开辟了N个空间// O(n)long[] fibonacci(int n) {long[] fibArray new long[n 1]; // 重新申请了一个数组来存放数据fibArray[0] 0;fibArray[1] 1;for (int i 2; i n ; i) {fibArray[i] fibArray[i - 1] fibArray [i - 2];}return fibArray;}例3 计算阶乘递归Factorial的空间复杂度 // 计算阶乘递归Factorial的空间复杂度// 递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间 O(n)long factorial(int N) {return N 2 ? N : factorial(N-1)*N;}4. 总结
结合代码的实现去做 空间和时间复杂度的计算一些常用的复杂度大小 O(1) O(log2^n) O(n) O(n*log2的n次) O(n的平方)
