算法是一系列解决问题的清晰指令,不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
一、算法的特征:

  • 输入项/输出:算法有0个或多个输入;算法至少有一个或多个输出。
  • 有穷性:算法必须能在执行有限个步骤之后终止。
  • 确切性:算法的每一步骤必须有确切的定义,无二义。
  • 可行性:算法每一步必须可行,每个计算步都可以在有限时间内完成。

二、算法设计的要求
1.正确性
2.可读性
3.健壮性(指一个算法对不合理数据输入的反应能力和处理能力,也称为容错性。)
4.时间效率高而存储量低

三、函数的渐进增长
1.函数的渐进增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n > N,f(n)总是比g(n)大,那么,我们说f(n)的渐近增长快于g(n)。
2.注意关注函数最高次幂的变化,忽略次要项与乘数。
3.某个算法,随着n的增大,它会越来越优于(差于)另一算法。

四、算法的时间复杂度(一般指最坏时间复杂度)
(1)进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而确定T(n)的数量级。算法的时间复杂度记作:T(n)=O(f(n))。这表示随着问题规模n的增大,算法执行的时间的增长率和 f(n) 的增长率成正比,所以 f(n) 越小,算法的时间复杂度越低,算法的效率越高。

(2)我们用O()来体现算法时间复杂度的记法,称作大O记法。

推导大O阶:
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中,只保留最高阶项。
3.如果最高阶项存在且不是1,则删除与这个项相乘的常数。
最后得到的结果就是大O阶。

得到的结果就是大O阶。

(3)常见的时间复杂度:

常用时间复杂度所耗费的时间从小到大排序:

前六种为多项式时间关系。后三者为指数时间的关系,通常不讨论。

  • 循环的时间复杂度=循环体的复杂度*循环运行次数。

(4)算法空间复杂度
S(n)=O(f(n))
完全可以用空间换时间,但没有必要。