专题一: 算法基础

1. 算法的定义及特点

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出. 数学函数可理解为是算法的一种特殊形式.

以梯度下降法求极值问题为例:

1.1 算法的基本特征

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

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

1.2 算法的基本要素

数据对象的运算和操作：计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类:

• 1.算术运算：加减乘除等运算
• 2.逻辑运算：或、且、非等运算
• 3.关系运算：大于、小于、等于、不等于等运算
• 4.数据传输：输入、输出、赋值等运算

1.3 算法的评定

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

(1). 时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模 $n$ 的函数 $f(n)$，算法的时间复杂度也因此记做：

$$t(n)=O(f(n))$$

因此，问题的规模 $n$ 越大，算法执行的时间的增长率与 $f(n)$ 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。
(1) 空间复杂度
算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
(2) 正确性
算法的正确性是评价一个算法优劣的最重要的标准。
(3) 可读性
算法的可读性是指一个算法可供人们阅读的容易程度
(4) 鲁棒性
鲁棒性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。

2 算法常见执行方法

2.1 判断语句

• if-else 判断语句

if语句的一般形式如下：

if 表达式: 语句1
else: 语句2

if语句中的“表达式”可以是关系表达式、逻辑表达式，甚至是数值表达式。其中最直观、最容易理解的是关系表达式。所谓关系表达式就是两个数值进行比较的式子。

a,b = 5,2
if a < b:print('两个数中的最小值为: ', a)
else:print('两个数中的最小值为: ', b)

两个数中的最小值为: 2

• if-elif-else 判断语句

name=input("Please input your name：")
if name=="Johnson":print("Hello my son.")
elif name=="Judy":print("Hello my daughter.")
elif name=="Aric":print("Hello my friend.")
elif name=="John":print("Hello to myself.")
else:print("Hello others.")

Please input your name：John
Hello to myself.

2.2 循环语句

• For 循环

for循环是编程语言中一种循环语句，而循环语句由循环体及循环的判定条件两部分组成，其表达式为：for单次表达式;条件表达式;末尾循环体: 中间循环体。如:

for i in range(5):print('Hello, world! \n')

Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!

• while 循环

t = 0
while t < 5:print('Hello, world! \n')t = t+1

Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!

2.3 综合运用

for y in range(1,10):for x in range(1,y+1):print('%dX%d=%d'%(x,y,x*y),end=' ')print(' ')

1X1=1
1X2=2 2X2=4
1X3=3 2X3=6 3X3=9
1X4=4 2X4=8 3X4=12 4X4=16
1X5=5 2X5=10 3X5=15 4X5=20 5X5=25
1X6=6 2X6=12 3X6=18 4X6=24 5X6=30 6X6=36
1X7=7 2X7=14 3X7=21 4X7=28 5X7=35 6X7=42 7X7=49
1X8=8 2X8=16 3X8=24 4X8=32 5X8=40 6X8=48 7X8=56 8X8=64
1X9=9 2X9=18 3X9=27 4X9=36 5X9=45 6X9=54 7X9=63 8X9=72 9X9=81

3. 计算复杂度

4. 代码的重用

5. 类函数的定义与使用

类函数是非常有用的工具, 可以把诸多函数封装起来, 只保留参数和数据两个结构, 这也是 python 机器学习中常用的调用格式. 而初学者对类的学习通常都感觉不容易, 通过编程书上利用动物类,猫啊狗啊的例子,或者人作为类,张三李四具体化, 越讲越糊涂.

其实对类的理解在不断运行代码的过程中很容易理解, 就是避免反复编译函数而生的, 而且无需每次都要考虑一系列函数的逻辑关系. 对于一个算法、一篇论文、一个大的项目, 类无疑是最方便的, 而且 python 语言的类定义更加的简单, 易读.

下面通过一个例子可以了解一下类的写法和功能

5.1 定义类

本案例是给定一个由数组组成的列表, 先转化成向量, 然后把向量前 $k$ 个元素相加求和, 并显示结果的过程. 本例中数据和参数$k$ 可随意更改, 类只需要提前编译一次即可,可反复利用. 使用方法和sklearn库类似, 两句话:(1) 生成空模型; (2) 利用 fit(x) 喂数据.

import numpy as np# 类的优势是把所有函数封装起来,只保留数据和参数接口, 当数据和参数变化时,无需重新运行类函数
class VECTOR_SUM:# 初始化模型参数def __init__(self, num=4):self.num = num# 定义类函数,可以通过 self 为其它函数调用def string2array(self,s):v = np.array(s)return v# 类的主要函数, 是数据的接口def fit(self,s):temp = self.string2array(s) # 调用类内函数时需要用到 selfsummation = np.sum(temp[0:self.num]) # 调用类内参数时需要用到 selfreturn summation

5.2 调用类函数

if __name__ == "__main__":x = [1,2,3,4,5,6,7,8] # 生成数据,可反复修改而无需重新编译类函数model = VECTOR_SUM(num=5) # 调用空模型,可设置参数summation = model.fit(x) # 类和数据的接口print("summation is : ", summation)

输出

summation is :  15