算法基本概念

5个特性：

1）有穷性

2）确定性

3）可行性

4）输入

5）输出

评价算法的优劣：

1）

时间复杂度

它定性描述算法的运行时间。一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。

时间复杂度又分为：

最坏时间复杂度

，

平均时间复杂度

，

最好时间复杂度

。

最坏时间复杂度是指最坏情况下，算法的时间复杂度。

平均时间复杂度是指所有输入实力在等概率出现的情况下，算法的期望运行时间。

最好时间复杂度是指最好情况下，算法的时间复杂度。

算法时间复杂度应该不难求解吧。

如果循环主体中的变量参与循环条件的判断，这时候计算循环体里面的操作次数，得出时间复杂度。

如果循环主体中的变量与循环条件无关，就采用数学归纳法或间接累计循环次数。

可能觉得有点模糊，不如做两道题，自然茅舍顿开。

常见的渐进时间复杂度为：





O

(

1

)

<

O

(

l

o

g

2

n

)

<

O

(

n

)

<

O

(

n

l

o

g

2

n

)

<

O

(

n

2

)

<

O

(

n

3

)

<

o

(

2

n

)

<

o

(

n

!

)

<

o

(

n

n

)

O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < o(2^n) < o(n!) < o(n^n)






O


(


1


)




<








O


(


l


o


g


2


n


)




<








O


(


n


)




<








O


(


n


l


o


g


2


n


)




<








O


(



n










2









)




<








O


(



n










3









)




<








o


(



2










n









)




<








o


(


n


!


)




<








o


(



n










n









)







2）

空间复杂度

空间复杂度S(n) 就是该算法所耗费的存储空间，是一个问题规模n的函数。这里有一点要注意，就是

算法原地工作是指算法所需的辅助空间为常量，即O(1)

。

如果觉得本文对你有帮助的话，不妨关注作者一波,小小的关注其实对我很重要。更多高质量内容与资料请访问：

数据结构简单学

，个人主页：

修心的小屋


如果喜欢的话，不妨关注一波，谢谢啦。