算法的基本概念

算法

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

上面这句话是官方定义，太复杂了，简单来说就是：解题的技巧和方式。

算法的特点包括：

• 输出
  • 至少有一个或多个输出。
• 输入
  • 至少有一个或多个输入。
• 有穷性
  • 指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
• 确定性
  • 算法的每一个步骤都具有确定的含义，不会出现二义性。
    算法在一定条件下，只有一条执行路径，相同的输入只有一条执行路径，相同的输入只能由唯一的输出结果。
• 可行性
  • 算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。

算法设计的要求包括正确性、健壮性、可读性。

算法效率

事后统计法
通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。

事后统计法的缺陷：

1. 要依据算法，之前先编好程序。
2. 时间的比较依赖计算机的硬件和软件，还有环境因素。
3. 测试数据设计困难。

事前分析评估方法
在计算机程序编制前，依据统计方法对算法进行估算。
算法效率的高低因素来自以下几点：

1. 算法采用的策略、方法
   • 算法好坏的根本。
2. 编译产生的代码质量
   • 由软件来支持。
3. 问题的输入规模
4. 计算机执行指令的速度
   • 看硬件的性能。

抛开硬件软件的因素，可以这样总结：
一个程序在运行时间上是依赖于算法的好坏和问题的输入规模。

算法时间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

时间复杂度的记法：
大O记法：O(\ \ )
一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。

分析一个算法的时间复杂度的方法：

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

线性阶

线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常需要确定某个特定语句或某个语句集运行的次数。因此，我们要分析算法的复杂度，关键就是要分析循环结构的运行情况。
C 语言例：

int i, n=100, sum=0;
for(i=0; i<n; i++)
{
    sum = sum + i;
}

该例时间复杂度为 O(n)，因为循环体中的代码需要执行 n 次。

平方阶

如果是嵌套呢？

循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。

C 语言例：

int i,j,n=100;
for(i=0; i<n; i++)
{
    for(j=0; j<n; j++)
    {
        printf("I love learnku.com\n");
    }
}

该例时间复杂度为 O(n2)。
如果由三个这样的嵌套循环，时间复杂度将会是 O(n3)。

对数阶

C 语言例：

int i=1, n=100;
while(i<n)
{
    i = i * 2;
}

每次 i * 2 之后，就距离 n 更近一步，假设有 x 个 2 相乘后大于或等于 n，则会退出循环。

2x=n 得到 x=log(2)n，所以这个循环的时间复杂度为 O(logn)

常见的时间复杂度所消耗时间的大小排列：

O(1)< O(\log n)< O(n)< O(n\log n)< O(n^2)< O(2n)< O(n!)< O(n^n)

最坏情况和平均情况

查找一个有 n 个随机数字数组中的某个数字，最好的情况是第一个数组就是，那么算法的时间复杂度为 O(1)，但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是 O(n)，这是最坏的一种情况了。
A H U J I L O P
H U J I L O P A

最坏情况运行时间是一种保证，运行时间=最坏情况的运行时间。
平均运行时间是期望的运行时间。平均的查找时间=n/2 次后发现目标元素。

对算法的分析
平均时间复杂度：计算所有情况的平均值
最坏时间复杂度：计算最坏情况下的时间复杂度

在没有特殊说明的情况下，都是指最坏时间复杂度。

空间复杂度

空间复杂度表示的是存储空间的复杂度，而不是算法的时间复杂度。
案例问题：
给出一个年费，计算出该年份是否是闰年。
这个问题可以设计一个算法，输入一个年份，通过算法的执行，之后得到是否是闰年的结果。
这个问题也可以事先给出一张年份表，每个年份有对应值 0 或者 1，1 代表该年是闰年，0 代表不是闰年。
这样的话就把问题巧妙的转化成了一个查找问题，直接查找输入年份的对应值就能得到结果。这样的做法优化了时间复杂度，但增加了空间复杂度，因为需要开辟一块空间来存储这张年份表。

当不用限定词的时候，直接说复杂度的时候，通常都指的是时间复杂度。

本作品采用《CC 协议》，转载必须注明作者和本文链接