Algorithm

Abstract

That’s from Wikipedia

Algorithm, in mathematics and computer science, is a series of well-defined specific calculation steps, which are commonly used in calculation, data processing and automatic reasoning. As an effective method, the algorithm is used to calculate functions. It contains a series of well-defined instructions, which can be clearly expressed in limited time and space. The instruction in the algorithm describes a calculation. When it is running, it can start from an initial state and initial input (possibly empty), and then through a series of limited and clearly defined states, it produces output and stops in a final state. The transition from one state to another is not necessarily deterministic. Some algorithms, including randomization algorithm, contain some random inputs

[TOC]

算法设计评价基本标准

算法是对特定问题求解步骤的一种描述，如果将问题看作函数，那么算法是把输入转化为输出

算法:

是对特定问题求解步骤的一种描述，是为了解决一个或者一类问题给出的 一个确定的、有限长的操作序列。

算法的设计依赖于数据的存储结构，因此对确定的问题，应该需求子啊适宜的存储结构上设计出一种效率较高的算法

算法的特性：

有穷性：

对于任何一组合法的输入值，在执行有穷步骤之后一定能结束，即算法中的操作步骤为有限个，并且每个步骤都能在有限的时间内完成

确定性：

对于每种情况下所应该执行的路径的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行；并且在确切的条件下只有唯一一条执行流程路径

可行性：

算法中的所有操作都必须足够基本，都可以通过已经实现的基本运算执行有限次实现

有输入:

作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法的执行过程中输入，而有些算法表面上没有输入，但实际上已被嵌入算法之中

有输出：

它是一组与“输入”有确定关系的量值，是算法进行信息加工可以得到的结果。这种确定关系即为算法的功能

算法设计目标：

正确性：

算法应满足具体问题的需求，正确反映求解问题对输入、输出加工处理等方面的需求

1. 程序中不含语法错误，计算的结果却不能满足规格说明要求。
2. 程序对于特定的几组输入数据能够得出满足要求的结果，而对于其他的输入数据的不出正确的计算结果；
3. 程序对于精心选择的、经典、苛刻且带有刁难性的几组输入数据能够得到满足需求的结果；（正确的算法）
4. 程序对于一切合法的输入数据都能得出满足要求的结果

可读性：

算法处理用于编写程序子啊计算机上执行之外，另一个重要用处是阅读和交流。

算法中加入适当的注释，介绍算法的设计思路、各个模块的功能等一些必要性的说明文字来帮助读者理解算法。

要求:

算法中加入适当的注释，介绍算法的设计思路、各个模块的功能等一些必要性的说明文字来帮助读者理解算法

对算法中出现的各种自定义变量和类型能做到“见名知义”，即读者一看到某个变量（或类型名）就能知道其功能

健壮性：

当输入数据非法时，算法能够适当地做出反应或进行处理，输出表示错误性质的信息并终止执行，而不会产生莫名其妙的输出结果。

时间效率与存储占用量：

一般来说，求解同一个问题若有多种算法，则

执行时间短的算法效率高

占用存储空间少的算法较好

算法的执行时间开销和存储空间开销往往相互制约，对高时间效率和低存储占用的要求只能根据问题的性质折中处理

算法复杂度

算法的时间复杂度：

算法的效率指的是算法的执行时间随问题“规模”（通常用整型量n表示）的增长而增长的趋势

“规模”在此指的是输入量的数目，比如在排序问题中，问题的规模可以是被排序的元素数目

假如随着问题规模n的增长，算法执行时间的增长率和问题规模的增长率相同则可记为：

T（n） = O（f(n)）

f(n) 为问题规模n的某个函数； T（n）被称为算法的（渐进）时间复杂度（Time Complexity） O表示法不需要给出运行时间的精确值； 选择f（n），通常选择比较简单的函数形式，并忽略低次项和系数 常用的有O（1）、O（logn）、O（n）、O（nlogn）、O（n*n）等等 多项式时间复杂度的关系为： O(1) < O(logn) < O(n) < O(N logn) < O(n²) < O(n³) 指数时间算法的关系为： O（2(n方)）< O(n!) <O(n(n方))

由于估算算法时间复杂度关心的只是算法执行时间的增长率而不是绝对时间，因此可以忽略一些因素。

方法：从算法中选取一种对于所研究的问题来说是“基本操作”的原操作，以该“基本操作”在算法中重复执行的次数作为算法时间复杂度的依据。

两个n x n 的矩阵相乘，求其时间复杂度

for i in range(10):    for j in range(10):

问题规模是矩阵的阶n,算法的控制结构式双重循环，基本操作是乘法操作 乘法执行次数为n²，则算法的时间复杂度为O(n²)

算法的空间复杂度：

算法在执行期间所需要的存储量包括：

1. 程序代码所占用空间
2. 输入数据所占用空间
3. 辅助变量所占用的空间

为了降低复杂度，一个直观的思路是：梳理程序，看其流程中是否有无效的计算或者无效的存储。我们需要从时间复杂度和空间复杂度两个维度来考虑。

常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划等，

降低空间复杂度的方法，就要围绕数据结构做文章了。

降低空间复杂度的核心思路就是，能用低复杂度的数据结构能解决问题，就千万不要用高复杂度的数据结构。

如何评定一个程序算法的好坏？

简而言之：在符合算法设计标准的前提下，运行的更快、所用计算资源更少。即是更好的算法

请注意这里的比较级别词更！！！，对于算法，个人认为就是获得同一结果的同时探究最优解决之道

算法优化的思维与方向？

降低复杂度，直观的思路是：

梳理程序，看其流程中是否有无效的计算或者无效的存储。我们需要从时间复杂度和空间复杂度两个维度来考虑。

常用的降低时间复杂度的方法：

• 递归、二分法、排序算法、动态规划，缓存算法等

降低空间复杂度的思路：

主要从数据结构方面思考

降低空间复杂度的核心思路就是，能用低复杂度的数据结构能解决问题，就千万不要用高复杂度的数据结构。

当然，时间与空间常常不可得兼，现实中一般更倾向时间。合适的算法和数据结构数据结构 即可产生化学反应

如何优化算法？

思路有：有效计算， 升维、时空转换

例如：我们要对n中最大的数，那么我们就需要把所有的数都判断一次。如果需要下次能够快速的找到，就需要排序。

有效计算：

在满足算法性质下，将无用的计算剔除。从而减少计算量，达到加速的效果

升维：

别人每次走一步，我们一次走两步或者三步。那么就可以更快

时空转换：

缓冲&缓存 例如：1 + 1 + 1 = 3为例子，为得到正确答案，方法是多种多样的。计算方面：三个1相加，2 + 1 或 1 + 2 简单的理解为：我记住”答案“，从而减少计算。

优化实例

本次作为一次思维开拓的分享，本次的选题可能会太过于简单。

但请不要着急，仔细与我交流，我相信你我都会有对对应的提升。

立已知、思未知。明限制

思考如何从 已知 -> 未知 ，中间 就是我们所需要补齐的桥梁。

1. 暴力法 + 优化
2. 引入 其他算法 + 数据结构
3. 多种解法
4. 最适合的解法

说了这么多，来道简单的算法题目导入（同一计算机，i5, python）

需求如下：累计求和1-n的值(1. 为防止误差，验证10次; 2. 验证每次计算次数)

# 在同一空间复杂下(也就是说没有迭代，探究暴力解法与高斯算法)# n = 100000# Method one 代码如下def func(n):
    start = time.time()
    count = 0
    theSum = 0
    for i in range(n + 1):
        theSum = theSum + n
        count += 1
    end = time.time()    return theSum, end - start, countfor i in range(10):
    print(f"Sum is %d Required %10.10f seconds count = %d" % func(10000))# %10.10f 表示取10位小数，运行结果如下

高斯算法，从1累加至n,等于(首项+尾项)*项数/2，等差数列通项公式

# Gaussian算法，无迭代算法
def fun1(n):
    start = int(time.time())
    theSum = (n * (n + 1)) / 2
    end = int(time.time())
    return theSum, end - start, n / 2

for i in range(1000000):
    print(f"Sum is %d Required %10.100f seconds count = %d" % fun1(50**100))