算法特性和算法复杂度

程序=数据结构+算法。

算法:

算法就是解特定问题的方法,是对特定问题求解步骤的一种描述。算法是计算机学科中最具方法论性质的核心概念,是计算机科学的灵魂

算法特性:5个特性

1.有穷性。必须执行有究步有限的时间内可以结束,不能一直执行下去。不然就成了无穷性就没有实际意义。

2.确定性。每一步都有要确切的含义,对相同输入要有相同的输出。

3.可行性。也就是说通过执行基本操作有限次可以实现。

4.算法有零个或多个输入。要有处理对象,也可以说是数据。可以通过嵌入到算法中(零个输入),或通过赋值方法使变量获得数据(一个或多个输入)。

5.算法有零个或多个输出。一个算法一定要有输出,也就是执行结果。可以返回数据,或是执行某个行为。

算法时间复杂度:

算法的时间复杂度是评估算法的重要标准之一,它能较了地体现算法本身的时间效率,而与具体实现算法的计算机软件、硬件无关。

分析一个算法的进间复杂度首先要从中选取一种能在很大程度上体现该算法执行时间的基本操作,以该基本操作重复执行的次数作为度量

一般情况下,算法基本操作重复执行的次数是问题规模n的某个函数f(n)。而算法的时间复杂度简单来说是指算法中某种基本操作执行次数的数量级。通常用T(n)=O(f(n))表示,其中O表示f(n)的数量级

例如:在矩阵相乘的算法中,乘法就是基本操作。

问题规模为n,基本操作乘法的执行次数f(n) ≈n*n*n,所以T(n)=O(n³)。

算法空间复杂度:

与算法时间复杂度类似,算法空间复杂度作为算法所需存储空间的量度,记作:

S(n)=O(f(n))

n是问题的规模,算法所需的存储空间是问题规模n的函数f(n)。算法空间复杂度也重要,但相对于时间复杂度来讲并没哪么重要(因为现在电脑内存都比较大)但在设计算法时“时、空”都要考虑进去,尽量避免存储空间的浪费。