算法时间复杂度的定义：
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)= O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。
一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法
1585982163593.jpg
常用的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
空间复杂度的定义:
算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
通常，我们都是用“时间复杂度”来指运行时间的需求，是用“空间复杂度”指空间需求。
当直接要让我们求“复杂度”时，通常指的是时间复杂度。
关于时间复杂度的一些练习
#include <stdio.h>
/*大O表示法
1. 用常数1取代运行时间中所有常数 3->1 O(1)
2. 在修改运行次数函数中,只保留最高阶项 n^3+2n^2+5 -> O(n^3)
3. 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3
*/
/*
时间复杂度术语:
1. 常数阶
2. 线性阶
3. 平方阶
4. 对数阶
5. 立方阶
6. nlog阶
7. 指数阶(不考虑) O(2^n)或者O(n!) 除非是非常小的n,否则会造成噩梦般的时间消耗. 这是一种不切实际的算法时间复杂度. 一般不考虑!
*/
/* 1. 常数阶时间复杂度计算 O(1) */
//1+1+1 = 3 O(1)
void testSum1(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum1:%d\n",sum);//执行1次
}
//1+1+1+1+1+1+1 = 7 O(1)
void testSum2(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum2:%d\n",sum);//执行1次
}
//x=x+1; 执行1次
void add(int x){
x = x+1;
}
/*2.线性阶时间复杂度*/
//x=x+1; 执行n次 O(n)
void add2(int x,int n){
for (int i = 0; i < n; i++) {
x = x+1;
}
}
//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
int i,sum = 0; //执行1次
for (i = 1; i <= n; i++) { //执行n+1次
sum += i; //执行n次
}
printf("testSum3:%d\n",sum); //执行1次
}
/*3.对数阶*/
/*2的x次方等于n x = log2n ->O(logn)*/
void testA(int n){
int count = 1; //执行1次
//n = 10
while (count < n) {
count = count * 2;
}
}
/*4.平方阶*/
//x=x+1; 执行n*n次 ->O(n^2)
void add3(int x,int n){
for (int i = 0; i< n; i++) {
for (int j = 0; j < n ; j++) {
x=x+1;
}
}
}
//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2
void testSum4(int n){
int sum = 0;
for(int i = 0; i < n;i++)
for (int j = i; j < n; j++) {
sum += j;
}
printf("textSum4:%d",sum);
}
//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n){
int i,j,x=0,sum = 0; //执行1次
for (i = 1; i <= n; i++) { //执行n+1次
for (j = 1; j <= n; j++) { //执行n(n+1)
x++; //执行n*n次
sum = sum + x; //执行n*n次
}
}
printf("testSum5:%d\n",sum);
}
/*5.立方阶*/
void testB(int n){
int sum = 1; //执行1次
for (int i = 0; i < n; i++) { //执行n次
for (int j = 0 ; j < n; j++) { //执行n*n次
for (int k = 0; k < n; k++) {//执行n*n*n次
sum = sum * 2; //执行n*n*n次
}
}
}
}
int main(int argc, const char * argv[]) {
testSum1(100);
testSum2(100);
testSum3(100);
return 0;
}
关于时间复杂度和空间复杂度的习题
1、设n是描述问题规模的非负整数，下面程序段的时间复杂度是（）
int x = 2;
while(x < n/2)
x = 2 * x;
A.O()
B.O(n)
C.O(n)
D.O(n2)
答案：A.程序中基本语句x=2*x；执行的次数为k，执行k时：x=2k+1.循环结束条件x<n/2,可以计算出x=2k+1，k = + C（C为常数），因此T(n) = O(
)
2、下面程序段的时间复杂度（）
int count = 0;
for(k=1;k<=n;k*=2)
for(j=1;j<n;j++)
count++
A.O()
B.O(n)
C.O(n)
D.O(n2)
答案：C.内层循环条件j <= n 与外层循环变量无关，每次循环j自增1，每次内循环都执行n次。所以内层循环的时间复杂度时O(n)。外层循环条件为k <= n，增量定义为k =2，可知循环次数为2k <= n,即k <= .所以外层循环的时间复杂度是O(
)。对于嵌套循环，时间复杂度是每个复杂度相乘，所以T(n) = O(n
)
3、某算法的语句执行频度为:(3n + n + n2 +8),其时间复杂度表示()
A.O()
B.O(n)
C.O(n)
D.O(n2)
答案：D.在计算时间复杂度时，可以忽略所有低次幂项和最高次幂项的系数。
4、假设一位数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）
A.O(1)
B.O(n)
C.O(n)
D.O(n2)
答案：A.读取第i个数组元素可以直接通过数组的下标定位，与n无关，因此时间复杂度为O(1).
5、下面算法将一维数组a中的n个数逆序存放到原数组中，空间复杂度为（）
for(int i =0;i<n;i++)
b[i] = a[n-i-1];
for(int i = 0;i<n;i++)
a[I] = b[I];
A.O(1)
B.O(n)
C.O()
D.O(n2)
答案：B.算法的空间复杂度只需分析算法在实现时所需要的辅助空间和问题规模n的函数关系。该算法需要另外借助一个大小为n的辅助数组b，所以其空间复杂度为O(n)
6、下面算法将一维数组a中的n个数逆序存放到原数组中，空间复杂度为（）
for(int i =0;i<n/2;i++)
{
int t = a[I];
a[i] = a[n-i-1];
a[n-i-1] = t;
}
A.O(1)
B.O(n)
C.O()
D.O(n2)
答案：A.因为该算法仅需要借助一个变量t，与问题规模n大小无关，所以空间复杂度为O(1).
7、下面说法正确的是（）
A.一个算法的空间复杂度大，则其时间复杂度也一定大
B.一个算法的空间复杂度大，则其时间复杂度也一定小
C.一个算法的时间复杂度大，则其空间复杂度也一定小
D.以上说法都不对
答案: D.算法的时间复杂度和空间复杂度没有直接关系。
8、分析下列算法的时间复杂度
int x = 90,y = 100;
while(y>0)
if(x > 100)
{
x = x -10;
y--;
}else{
x++;
}
答案：O(1),程序中基本语句“y--”，“x++”执行次数是由x和y决定的，而x和y都是一个常数，所以T(n) = O(1).
9、分析下面算法的时间复杂度
for(int i =0;i<n;i++){
for(int j = 0;j<m;j++){
a[i][j] = 0;
}
}
答案：O(nm),由于程序为嵌套循环，外层循环执行次数为n，内层循环次数为m，所以T(n) = O(nm).
10、分析下面算法的时间复杂度
int x = n;//n>1
int y = 0;
while(x >= (y+1)*(y+1)))
y++;
答案：O(sqrt(n)).基本语句“y++”的执行次数为f(n),则x >= (f(n)+1)2,由于x = n，所以f(n) <= sqrt(n) - 1;即T(n) = O(sqrt(n));
网友评论