时间复杂度与空间复杂度详解

• （一）时间复杂度和空间复杂度的作用？
• （二）时间复杂度和空间复杂度如何计算？
• • （1）时间复杂度
  • • 具体案例分析
    • 时间复杂度的比较
  • （2）空间复杂度
  • • 两种常见空间复杂度

企业建站必须是能够以充分展现企业形象为主要目的，是企业文化与产品对外扩展宣传的重要窗口，一个合格的网站不仅仅能为公司带来巨大的互联网上的收集和信息发布平台，创新互联公司面向各种领域：玻璃钢坐凳等网站设计、成都全网营销推广解决方案、网站设计等建站排名服务。
（一）时间复杂度和空间复杂度的作用？

答：度量算法的效率

1. 时间复杂度：用来衡量执行算法所花费的时间；
2. 空间复杂度：用来衡量执行算法所占用的空间；

（二）时间复杂度和空间复杂度如何计算？ （1）时间复杂度

频度：一个语句的频度是指该语句在算法中被执行的次数。

时间复杂度，即分析算法中所有语句的频度之和T(n)的数量级。
因为算法中最深层循环内的语句的频度与T(n)同量级，因此通常采用算法中最深层循环内语句的频度f(n)来分析算法的时间复杂度。将其记作： T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))

注意： 在实际计算中，一般取f(n)中随n增长最快的项，将其系数置为1作为时间复杂度的度量。
例如：f(n)=an³+bn²+cn 的时间复杂度为 O(n³)；f(n)=5 的时间复杂度为O(1)

具体案例分析

1. 类型一：

void func(n){int i,j;
	for(i=0;ifor(j=i;j	printf("每天进步一点点");
		}
	}
}

分析：
① 找最深层循环内的语句的频度，即printf("每天进步一点点");的执行次数；

• 当 i=0 时—— j 对应深层循环执行 n 次
• 当 i=1 时—— j 对应深层循环执行 n-1 次
• …
• 当 i=n-1 时—— j 对应深层循环执行 1 次
• 则最深层循环语句执行次数为： n ( n + 1 ) 2 \frac{n(n+1)}{2} 2n(n+1)​

② 取f(n)中随n增长最快的项，将其系数置1，即该函数的时间复杂度为 O(n²) 。

2. 类型二：

void func(n){int i;
	for(i=1;iprintf("每天进步一点点");
	}
}

分析：
① 找最深层循环内的语句的频度，即printf("每天进步一点点");的执行次数；

• 当循环内语句执行次数为 1 时—— i=1
• 当循环内语句执行次数为 2 时—— i=2
• 当循环内语句执行次数为 3 时—— i=2²
• …
• 当循环内语句执行次数为 k 时—— i= 2 k − 1 2^{k-1} 2k−1
• 则如果当 i= 2 k 2^{k} 2k 时不满足条件 i

② 取f(n)中随n增长最快的项，将其系数置1，即该函数的时间复杂度为 O( l o g 2 n log_2n log2​n) 。

时间复杂度的比较

O(1)常数阶< O(logn)对数阶< O(n)线性阶< O(n²)平方阶< O(n³)(立方阶)< O( 2 n 2^n 2n) (指数阶)

（2）空间复杂度

一个程序在执行时所需空间包括：存储本身所用的指令、常数、变量和输入数据的空间，以及对数据进行操作处理所申请使用的辅助空间等。

空间复杂度，使用S(n)来定义算法所耗费的存储空间，记作 S ( n ) = O ( g ( n ) ) S(n)=O(g(n)) S(n)=O(g(n))

两种常见空间复杂度

1. 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。例如：

void func(n){int i=1;
 int j=2;
 int k=i+j;//算法空间与n无关
}

2. 如果随着输入值 n 的增大，程序申请的临时空间也随之变化，则程序的空间复杂度需要具体分析，例如：

void func(n){int a[n];//所申请的空间随着n的取值而进行线性变化，空间复杂度为O(n)
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前标题：数据结构：时间复杂度和空间复杂度求解思路方法详解-创新互联
URL标题：http://lswzjz.com/article/dgjdgp.html