01-算法基础

算法定义和特征

定义：算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。

不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

一个算法应该具有以下五个重要的特征：

• 有穷性：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
• 确切性：算法的每一步骤必须有确切的定义；
• 输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
• 输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果，没有输出的算法是毫无意义的；
• 可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

算法设计要求

算法设计的要求:

• 确定性: 指的是算法至少应该有输入,输出和加工处理无歧义性，能正确反映问题的需求,能够得到问题的正确答案。确定性大体分为四个层次:

  1. 算法程序无语法错误;
  2. 算法程序对于合法的输入产生满足要求的输出;
  3. 对于非法输入能够产生满足规格的说明;
  4. 算法程序对于故意刁难的测试输入都有满足要求的输出结果。

• 可读性: 程序便于阅读,理解交流。

• 健壮性: 当输入数据不合法时,算法也能作出相关处理，而不是产生异常,崩溃或者莫名其妙的结果。

• 时间效率高和存储量低。

算法效率的度量方法

事后统计方法：主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低，但这种方法有很大缺陷，一般不予采纳。

事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。

一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于以下因素：

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

算法时间复杂度

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

根据定义，求解算法的时间复杂度的具体步骤是：

1. 找出算法中的基本语句；算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
2. 计算基本语句的执行次数的数量级；只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
3. 用大Ο记号表示算法的时间性能。将基本语句执行次数的数量级放入大Ο记号中。

如何推导大o阶呢？下面是基本的推导方法：

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

简单的说，就是保留求出次数的最高次幂，并且把系数去掉。 如T(n)=n2+n+1 =O(n2)

一些例子

# 复杂度O(1)
print("this is wd")
 
 
# 复杂度O(n)
n = 2
for i in range(n):
    print(i)
 
 
# 复杂度O(n2)
for i in range(n):
    for j in range(n):
        print(j)
 
 
# 复杂度O(n3)
for i in range(n):
    for j in range(n):
        for k in range(n):
            print('wd')
 
 
# 复杂度O(log2n)
while n > 1:
    print(n)
    n = n // 2

常见的复杂度按效率排序：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2nlogn)<O(n2)

常见的时问复杂度如表所示。

空间复杂度(Space Complexity)

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，这种算法是节省存储的算法；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。

如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

最坏情况与平均情况

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

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

而平均运行时间也就是从概率的角度看， 这个数字在每一个位置的可能性是相同的，所以平均的查找时间为n/2次后发现这个目标元素。平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。也就是说，我们运行一段程序代码时，是希望看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。一般在没有特殊说明的情况下，都是指最坏时间复杂度。