算法

算法的定义

解决问题的方法与步骤

算法的特性

输入性：一个算法必须具有零个或多个输入量

输出型：一个算法应有一个或多个输出量，输出量是算法计算的结果

确定性：算法中每一条指令应含义明确、无歧义，即对每一种情况、需要执行的动作都应严格地、清晰地规定

有穷性：算法的指令执行序列是有穷的

有效性：每条指令必须是足够基本的。也就是说，他们原则上都能精确到可用笔和纸来模拟实现其指令过程

算法的效率

算法在编写成可执行程序后，运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度 主要是用来衡量一个算法的运行快慢，而空间复杂度主要是衡量一个算法运行所需要的额外空间，在很早的时候，由于计算机发展的还不算完善，运行内存是很低的，从而导致程序员们在编写程序的时候，很看重空间复杂度，不过随着科技的发展，计算机也在进行飞一般的提升，现在，空间复杂度已经没有那么重要了，但是还是有一定作用的。

时间复杂度

算法执行所需的基本操作次数（即时间消耗）与问题规模 n 之间的关系

用大 O 表示法表示：只保留最高项，忽略常数、低阶项

C++程序 1s 的时间最多支持 10^8 量级的简单运算

算法的时间复杂度只与问题的规模有关系，和评估需要采用与运行环境、编译系统、硬件配置无关

常见时间复杂度	表示法	示例算法
常量阶	O(1)	访问数组元素
对数阶	O(logn)	二分查找
线性阶	O(n)	线性查找
线性对数阶	O(nlogn)	快速排序、归并排序
平方阶	O(n^2)	冒泡排序、选择排序
立方阶	O(n^3)
k 次方阶	O(n^k)
指数阶	O(2^n)	汉诺塔、部分递归算法
阶乘阶	O(n!)	全排列问题

时间复杂度的优劣对比：

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

时间复杂度越小，算法的效率越高

大O渐进表示法

1. 时间复杂度中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时， 低阶项对结果影响越来越小，当N无穷大时，就可以忽略不计了。

2. 如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大，这个系数 对结果影响越来越小，当N无穷大时，就可以忽略不计了。

3. T(N)中如果没有N相关的项目，只有常数项，用常数1取代所有加法常数。

时间复杂度计算示例

// 计算Func2的时间复杂度？
void Func2(int N)
{
    int count = 0;
    for (int k = 0; k < 2 * N ; ++ k)
    {
        ++count;
    }
    int M = 10;
    while (M--)
    {
        ++count;
    }
    printf("%d\n", count);
}

Func2 执行的基本次数：2N + 10

那么他的时间复杂度为：O（N）

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
    int count = 0;
    for (int k = 0; k < M; ++ k)
    {
        ++count;
    }
    for (int k = 0; k < N ; ++k)
    {
        ++count;
    }
    printf("%d\n", count);
}

Fun3执行的基本次数 M+N

通过大O渐进表示法就可以得出以上Fun3的时间复杂度会出现3种情况
若M>>N,O（M）
若M<<N,O（N）
若M==N，O（M+N）

// 计算Func4的时间复杂度？
void Func4(int N)
{
    int count = 0;
    for (int k = 0; k < 100; ++ k)
    {
        ++count;
    }
    printf("%d\n", count);
}

Fun4执行的基本次数
T(N)=100

通过大O渐进表示法就可以得出以上Fun4的时间复杂度为
O（1）

常见算法复杂度的对比

空间复杂度

首先，空间复杂度的计算方法其实和时间复杂度是差不多的，它们都是用的大O的渐进表示法，只不过时间复杂度是来计算运行次数的，而空间复杂度是来计算变量的个数的（这里涉及到了动态内存的开辟等等），这里值得一提的是：函数在运行时所需要的栈空间在编译期间已经确定好了，因此空间复杂度主要是针对于函数在运行的时候所申请的额外空间所确定的！

C++程序中内存限制一般支持数组开到 10^7 量级