算法：是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表现一个或多个操作。

算法的特性

输入输出：算法具有零个或多个输入，至少有一个或多个输出。
有穷性：指算法在执行有限的步骤后，自动结束而不会出现无限循环，并且每个步骤在可接受的时间内完成。（譬如运行二十年结束的算法就不可行）
确定性：算法的每一个步骤都具有确定的含义，不会出现二义性。（算法在一定条件下，只有一条执行路径，相同的输入只能有唯一输出的结果）
可行性：算法每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。（算法可以转换为程序上机运行，并能得到正确结果）

算法的设计要求

正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能得到问题的正确答案。

四个层次：

1.算法程序没有语法错误。

2.算法程序对于合法的输入数据能够产生满足要求的输出结果。

3.算法程序对于非法的输入数据能够得到满足规格说明的结果。

4.算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。

一般情况下把层次3作为一个算法是否成功的标准
可读性：算法设计的另一目的是为了便于阅读、理解和交流。
健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果
时间效率高和存储量低（存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序所占用的内存或外部存储空间）

算法效率的度量方法

事后分析法(不科学，不准确)
事前分析估算法

一个程序的运行时间，依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少

算法的时间复杂度：大O记法

推导大O阶

用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中，只保留最高阶项。
如果最高阶存在且不是1，则去除与这个项相乘的常数。

常数阶 O(1)

1
2
3

int sum = 0;       //执行一次
sun = (1+n)*n/2;   //执行一次
printf("%d",sum);  //执行一次

线性阶 O(n)

for (int i = 0;i < n;i++)
{
    //时间复杂度为O(1)的序列
}

对数阶 O(logn)

int count;
while (count < n)
{
    count = count * 2;
    //时间复杂度为O(1)的序列
}

平方阶 O(n²)

int i,j;
for (i = 0;i < n;i++)
{
    for (j = 0;j < n;j++)
    {
        //时间复杂度为O(1)的序列
    }
}

int i,j;
for (i = 0;i < n;i++)
{
    for (j = i;j < n;j++)
    {
        //时间复杂度为O(1)的序列
    }
}
/*
  总执行次数 = n+(n-1)+(n-2)+...+1
            = (n+1)*n/2
            = n²/2 + n/2
  时间复杂度仍为O(n²)
*/

void function(int count)
{
    int j;
    for (j = count;j < n;j++)
    {
        //时间复杂度为O(1)的序列
    }
}

n++;                                 //执行次数为1
function(n);                         //执行次数为n
int i,j;
for(i = 0;i < n;i++)                 //执行次数为n²
{
    functon(i);
}
for (i = 0;i < n;i++)                //执行次数为n*(n+1)/2
{
    for (j = i;j < n;j++)
    {
        //时间复杂度为O(1)的序列
    }
}
//时间复杂度仍为O(n²)

常见时间复杂度所消耗时间排序

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

其他

最坏运行时间是一种最重要的需求，除非特殊指定，一般提到的运行时间都是指最坏情况下的运行时间。

平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。

若算法执行时所需的辅助空间相对于数据量而言是一个常数，则称此算法为原地工作，空间复杂度为O(1).