初始算法

数据结构与算法

数据结构和算法是一名程序开发人员的必备基本功

>算法引入

如果a+b+c=1000，且a^2+b^2=c^2(a,b,c为自然数)，如何求出所有a，b，c可能的组合

枚举法

思路：

a = 0

b = 1

c = 0~1000

import time

start_time = time.time()

for a in range(0,1001):

    for b in range(0,1001):

        for c in range(0,1001):

            if a+b+c == 1000 and a**2 + b**2 == c**2:

                print("a,b,c:%d,%d,%d"%(a,b,c))

end_time = time.time()

print("times:%d"%(end_time-start_time))

print("end")

>算法的概念

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

算法是独立存在的一种解决问题的方法和思想。

对于算法而言，实现的语言并不重要，重要的是思想。

算法可以有不同的语言描述实现版本（如C描述、C++描述、Python描述等），我们现在是在用Python语言进行描述实现。

>算法的五大特性

1.输入: 算法具有0个或多个输入

2.输出: 算法至少有1个或多个输出

3.有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成

4.确定性：算法中的每一步都有确定的含义，不会出现二义性

5.可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成

>算法效率衡量

时间复杂度与大O记法

每台机器执行的总时间不同

但是执行基本运算数量大体相同

>时间复杂度的几条基本计算规则

1.基本操作，即只有常数项，认为其时间复杂度为O(1)

2.顺序结构，时间复杂度按加法进行计算

3.循环结构，时间复杂度按乘法进行计算

4.分支结构，时间复杂度取最大值

5.判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略

6.在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度

>常见时间复杂度

>常见时间复杂度之间的关系