威海医院网站制作,青海省住房和城乡建设厅门户网站,中国互联网,梅州建站教程文章目录 时间复杂度常数阶时间O(1)对数阶时间O(logN)线性阶时间O(n)线性对数阶时间O(nlogN)平方阶时间O(n*n) 空间复杂度常量空间O(1)线性空间O(n)二维空间O(n*n)递归空间 时间复杂度
常数阶时间O(1)
代码在执行的时候#xff0c;它消耗的时间并不随着某个变量的增长而增长… 文章目录 时间复杂度常数阶时间O(1)对数阶时间O(logN)线性阶时间O(n)线性对数阶时间O(nlogN)平方阶时间O(n*n) 空间复杂度常量空间O(1)线性空间O(n)二维空间O(n*n)递归空间 时间复杂度
常数阶时间O(1)
代码在执行的时候它消耗的时间并不随着某个变量的增长而增长那么无论这类代码有多长都可以用O(1)来表示它的时间复杂度我们知道常数项对函数的增长速度影响不大所以当T(n)C,C为一个常数的时候我们说这个算法的时间复杂度为O(1);如果T(n)不等于一个常数项时直接将常数项省略。
int i1;
int j2;
i;
j;
int mij;对数阶时间O(logN)
在while循环里面每次都将i乘以2乘完之后i距离n就越来越近了。我们试着求解一下假设循环x次之后i就大于n了此时这个循环就退出了也就是说2的x次方等于n,那么xn
int i1;
while(in)
{
ii*2;
}线性阶时间O(n)
for循环里面的代码会执行n遍因此它消耗的时间是随着n的变化而变化的如果T(n)不等于一个常数项时直接将常数项省略。因为函数的阶数对函数的增长速度的影响是最显著的所以我们忽略与最高阶相乘的常数.我们知道高次项对于函数的增长速度的影响是最大的同时因为要求的精度不高所以我们直接忽略低次项。或者说如果复杂度是多个n的函数之和则只关心随n的增长而增长得最快的那个函数。
int aFunc(int n){for(int i0;in;i){ //n1次printf(Hello,World!\n); //n次}return 0; //1次
}这个代码需要(n1n1)2n2次运算时间复杂度为O(n)
线性对数阶时间O(nlogN)
将时间复杂度为O(logN)的代码循环n遍的话那么它的时间复杂度就是n*O(logN),也就是O(nlogN)
for(m1;mn;m){int i1;while(in){ii*2;}
}平方阶时间O(n*n)
如果把O(n)的代码再嵌套循环一遍它的时间复杂度就是O()如果将其中一层循环的n改成m那它的时间复杂度就变成O(m*n)
for(x1;in;x){for(i1;in;i){ji;j;}
}【例1】N×N矩阵相乘
for(i1;in;i) //n1for(j1;jn;j){ //n*(n1)c[i][j]0; //n*nfor(k1;kn;k) //n*n*(n1)c[i][j]c[i][j]a[i][k]*b[k][j];//T(n)O(n*n*n)}用级数求和的方式去算
【例2】
for(i1;in;i)for(j1;j1;j)for(k1;kj;k)xx1;【例3】分析以下程序的时间复杂度
i1;
while(in)ii*2;关键是要找出来执行次数x与n的关系并完成n的函数。 若循环执行1次i1*22若循环执行2次i2*22^2若循环执行3次i22*223,……若循环执行x次i2^x 设语句ii*2执行次数为x次由循环条件in,所以2^xn所以xlog以2为底n 即f(n)log以2为底n取最大值f(n)log以2为底n 空间复杂度
常量空间O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化即此算法空间复杂度为一个常量可表示为O(1)
int i1;
int j2;
i;
j;
int mij;线性空间O(n)
这段代码中第一行new了一个数组出来这个数据占用的大小为n,这段代码的2-6行虽然有循环但没有再分配新的空间。因此这段代码的空间复杂度主要看第一行即可即S(n)O(n)
int[] mnew int[n];
for(i1;in;i)
{ji;j;
}【例】将一维数组a中的n个数逆序存放到原数组中。
【算法1】交换数组a中每一个位置的值
for(i0;in/2;i){ta[i]; //创建辅助空间t,变量t与n是多少没有关系.S(n)O(1)a[i]a[n-i-1];a[n-i-1]t;
}
【算法2】将a中所有元素依次倒着放入b数组
for(i0;in;i)b[i]a[n-i-1]; //创建辅助数组bb的大小和数组a的大小一样S(n)O(n)
for(i0;in;i)a[i]b[i];二维空间O(n*n)
当算法分配的空间是一个二维数组集合并且集合的长度和宽度都与输入规模n成正比时空间复杂度记作O()
int[][] matrixnew int[n][n];//O(n^2)
int[][] matrixnew int[m][n];//O(mn)递归空间
正如下面代码一样递归代码中没有显示声明变量或者集合但是计算机在执行程序时会专门分配一块内存用来存储“方法调用栈”。
void fun4(int n){if(n1){return;}fun4(n-1);...
}方法调用栈包括入栈和出栈两个操作 当进入一个新方法时执行入栈操作把调用的方法和参数信息压入栈中 当方法返回时执行出栈操作把调用的方法和参数信息从栈中弹出 还是上述代码假设现在传入参数5那么方法fun4(5)的调用信息先入栈 method fun4 n 5 接下来递归调用相同的方法方法fun4(4)的调用信息入栈 method fun4 n 4 method fun4 n 5 以此类推递归越来越深栈内的元素也越来越多最终 method fun4 n 1 method fun4 n 2 method fun4 n 3 method fun4 n 4 method fun4 n 5 当n1的时候触发递归的结束条件执行return,方法出栈。最终所有入栈的元素都会出栈。 由上面“方法调用栈”的出入栈过程可以看出执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的如果递归的深度是n那么空间复杂度就是O(n).
