大连网站设计公司排名/有创意的网络广告案例

1.算法效率

在数据结构中描述算法的效率有两种方法:一是时间效率,就叫做时间复杂度,二是空间效率,叫做空间复杂度

在计算机发展早期,因为存储容量小,所以空间复杂度就显得很重要,而随着计算机的发展,存储空间已经有了很大的飞跃,所以如今就减少了对空间复杂度的关注,而转向了时间复杂度 

2. 时间复杂度

时间复杂度:一个算法所花费的时间与其中语句的执行次数成正比,所以时间复杂度就是算法中的基本操作的执行次数

时间复杂度不是绝对意义上的快慢,而是随着数据规模的变化,运行时间的变化趋势

2.1  大O的渐进表示法

在实际中,计算时间复杂度不需要计算出精确的执行次数,而只需要大概执行次数,大O渐进表示法就是一个大概描述执行次数的方法

大O符号(Big O natation):用于描述函数渐进行为的数学符号

 大O渐进表示法:

(1)用常数1取代运行时间中的所有加法常数(最高次项化为1)

(2)在修改后的运行次数函数中,只保留最高次项

大O渐进表示法就是去掉后面那些对结果影响不大的项,简洁明了的表示出了执行次数 

 常见的时间复杂度:

所耗的时间从小到大:

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2n)<O(n!)<O(nn)

冒泡排序:O(n),二分查找:O(log2^n)通常写为(logn),阶乘:O(n),斐波那契数列:O(2^n)[很慢]

3. 空间复杂度

空间复杂度是一个算法在运行过程中额外占用存储空间的大小(不考虑输入/输出用到的空间)

空间复杂度也用大O渐进表示法表示

冒泡排序空间复杂度:O(1),斐波那契数列空间复杂度:O(n),阶乘O(n)

常见的时间和空间复杂度总结: