算法基础 | 算法基础

算法基础

算法定义

解决一个具体问题的方法称为一个算法

算法的特征

1）确定性：组成算法的每条指令清晰、无歧义
2）有限性：算法中每条指令的执行次数有限
3）可行性：每条指令是简单的、具体的
4）输入：有零个或多个外部量作为算法的输入
5）输出：算法产生至少一个量作为输出

算法是程序之灵魂

算法的优劣

• 时间复杂度：算法运行所需要的运算步骤

  通常表示为问题规模n的函数T(n)

• 空间复杂度：算法运行所需要的内存单元

  通常表示为问题规模n的函数S(n)

• 时空特性

• 稳定性
• 健壮性（鲁棒性）
• 可靠性
• 实现难度
• 模块化

算法的内容

• 算法设计

  针对具体问题，设计一个解决方案

  • 正确
  • 步骤尽量少
  • 占用空间尽量少
  • 实现简单
  • 其他

• 算法分析

  正确性分析-证明（归纳法）
  时空效率分析-计数
  时空特性分析-经验

Example 1:时间效率分析-计数

for(i=1;i<=n;i=2*i)
{
    for(j=1;j<=i;j++)
    {
        laugh++;
    }
}

result:1+2+…+2^ceil(log2 n) = 2^(ceil(log2 n)+1) - 1

Example 2:Horner 算法

Horner(int a[n],real x)
{
    real p = 0;
    for(i=0;i<=n;i++)
    {   
        p+=p*x*a[n-i];
    }
    return p;
}

算法时间复杂度分析

• 最坏情况时间复杂度—T(n)表示算法对规模为n的任意输入所需要的最大步骤
• 平均时间复杂度——T(n)表示算法对规模为n的所有输入所需的步骤的平均值
• 最好情况时间复杂度—T(n)表示算法对规模为n的任意输入所需要的最小步骤

• Big idea:渐进时间复杂度—当n增大时用T(n)的主要部分代替T(n)

  常用在理论分析中 理论分析与实际情况有可能不一致

e.g. 对a1 a2 … an-1 an 进行排序
最好情况：1 2 … n
最坏情况：n n-1 ..1
2 1 3 …n n-1

算法设计与分析的步骤

1. 问题的描述（Description）
2. 数据结构的选择(Selection)
3. 算法设计(Design)
4. 算法分析(Analysis)
5. 算法的实现(Implement)

Example 3:isPrime

isPrime(n)
{
    for(i=2;i<sqrt(n);i++)
    {
        if(n%i==0) return false
    }
    return true
}

Example 4:euclid

euclid(int a,int b)
{
    if(b==0) return a;
    else return euclid(b,a%b);
}