算法

定义

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

---

算法的特性

1.输入输出：算法具有零个或多个输入，算法至少有一个输出或多个输出。
2.有穷性：算法在执行有限个步骤之后，会自动结束而不会出现死循环，并且每一个步骤都在可接受的时间内完成。
3.确定性：算法的每一步骤都有明确的含义，不会出现二义性。
4.可行性：算法的每一步都必须是可行的，即每一步骤都可以执行有限次来实现。

---

算法设计的要求

1.正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反应问题的需求、能够得到问题的正确答案。
2.可读性：算法设计的另一目的是为了便于阅读、理解和交流；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。
3.健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名奇妙的结果。
4.高效率和底存储需求：设计算法应该尽量满足时间效率高和存储量底的需求。

---

算法效率的度量

1.事后统计方法：主要通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
缺点：一是必须先运行依据算法编制的程序；二是所得时间的统计依赖于，计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。

---

2.事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。一个高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
1）算法采用的策略、方法。
2）编译产生的代码质量。
3）问题的输入规模。
4）机器执行指令的速度。

---

算法时间复杂度

推导大O阶方法

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

---

常用的时间复杂度所消耗的时间从小到大一次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

---

举个求时间复杂度的栗子，看下面代码：

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

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

由代码可以知道程序执行的次数：
f(n)=1+n+ n² +n(n+1)/2 = 3n²/2+ 3n/2+1
根据推导大O阶方法，得到时间复杂度(n²)

最坏时间复杂度

最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种重要的需求，通常，除非特别指定，我们提到的运行时间都是在最坏情况的运行时间。

平均时间复杂度

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

对于算法的分析，一种方法是计算平均时间复杂度。另一种方法是计算最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

---

算法空间复杂度

算法空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称次算法为原地工作，空间复杂度为O(1)。（我的理解是，比如问题只需要开辟一个500*500的空间就可以完全存储所有输入数据，此时开辟的存储空间是固定大小，所以可以看作原地工作）