1.时间复杂度和空间复杂度

2018-11-17 本文已影响0人八斗东流

算法设计的要求:正确性,可读性,健壮性和效率与低存储量需求.

为了比较同一问题的不同算法,通常的做法是从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该操作的重复执行次数作为算法的时间量度.

例如:

for(i=1;i<=n;i++){

for(j=1;j<=n;j++){

sum=i*j;

}}

在代码中,乘法是该循环的基本操作,整个算法的执行与该基本操作重复的次数 $n^2$ 成正比,记作 $T(n)=O(n^2 )$ .

1.时间复杂度:

$T(n)=O(f(n))$

他表示随规模n的增大,算法执行时间的增长率和 $f(n)$ 的增长率相同,称为算法的渐进时间复杂度,简称时间复杂度.

如何使用时间复杂度描述?

首先我们需要确定一个基本操作n,根据这个基本操作的重复次数来表示O(f(n)).

例如常量阶O(1),线性阶O(n),平方阶O( $n^k$ ),对数阶O( $logN$ ),指数阶O( $2^n$ )等等.

看样子回头又得补高数了...

补充:由于算法的时间复杂度考虑的只是对于问题规模n的增长率,则在难以精确计算基本操作执行次数的情况下,只需求出它关于n的增长率或阶即可.

补充:for(i=1;i<=n;i++){a++};

for(i=1;i<=n;i++){for(j=1;j<=n;j++){a++;}

第一个for循环时间复杂度是O(n),第二个是O(n^2),那么整个就是O(n+n^2).

一般来说，只要算法中不存在循环语句，时间复杂度就为O(1)。

2.空间复杂度

通常来说，只要算法不涉及到动态分配的空间，以及递归、栈所需的空间，空间复杂度通常为O(1)；

一般的递归算法空间复杂度为O(n^2),