3分pk10规律_《从入门到放弃》数据结构和算法 1

  • 时间:
  • 浏览:2

1. 简介 

  最近将会快过年了,否有很忙碌了,人心浮动,很多很多都请假了,现在终于有时间来系统学习下和恶补一下常见数据形态和算法的知识,很多很多,还是通过记录笔记装入 博客的措施来督促自己学习。同去和小伙伴们分享一下学习心得与体会。算法对于很多很多守护程序运行运行员都接触非要的,何况是一另一个 测试人员。而且面试过程中,多有几个少否有算法题的面试。很多很多,学习算法,短期来看是为了跳槽准备,长期来看,是锻炼一另一个 人正确处理问提的思路的提升的一另一个 途径。

2. 算法的引入

  来看一另一个 问提:将会 a+b+c = 30, 且 a^2 + b^2 = c^2(勾股定理),如可求出所有a b c的组合。

2.1 问提分析:

  上端告诉另一个 条件,从数学角度来说,上端有十个 未知数,只另一个 表达式条件,让我们都都都第一反应是转加上二元二次方程来解答。这里让我们都都都是计算机通过代码来正确处理问提。字面意思很多很多 a的取值范围是0到30, b的取值范围是0到30, c的取值范围是0到30, 而且加上题目的另一个 表达式条件,利用for嵌套循环,计算机肯定能我想 们找出a b c的取值。

2.2 代码实现:

  根据上端的分析,python代码实现如下:

2.3 参考代码:

# coding=utf-8
# 1.先设置编码,utf-8可支持中英文,如上,一般装入

第一行

# 2.注释:包括记录创建时间,创建人,项目名称。
'''
Created on 2020-1-02
@author: 北京-宏哥
Project:《从入门到放弃》数据形态和算法 1- 算法的引入和算法时间错综复杂度
'''
# 3.导入模块

import time

start_time = time.time()
for a in range(0, 301):
    for b in range(0, 301):
        for c in range(0, 301):
            if a + b + c == 30 and a**2 + b**2 == c**2:
                print("a, b, c: %d, %d, %d" % (a, b, c))
end_time = time.time()
print(end_time - start_time)

2.4 运行结果:

  虽然 上端代码思路也是用到了一另一个 措施,叫枚举法,很多很多 一另一个 一另一个 列出来去尝试,不行,换下一另一个 值继续去匹配。

  运行代码后,控制台打印如下图的结果:

  也很多很多 差很多花费三分钟(117秒多),找出了符合条件的a b c的有一种取值组合。将会这麼计算机,人也是可不可不还能不能根据这一思路,一步一步去算,只不过时间更是问你有多慢。这一时间开销,让我们都都都很不满意,对用户来说,还是太慢了。有这麼哪几种措施提升以下计算时延。

2.5 优化上端代码:

  根据数学知识,让我们都都都用代码实现二元二次方程的思路,c = 30 - a - b; 来减少第三层嵌套for循环。

2.5.1 代码实现:

2.5.2 参考代码:
# coding=utf-8
# 1.先设置编码,utf-8可支持中英文,如上,一般装入

第一行

# 2.注释:包括记录创建时间,创建人,项目名称。
'''
Created on 2020-1-02
@author: 北京-宏哥
Project:《从入门到放弃》数据形态和算法 1- 算法的引入和算法时间错综复杂度
'''
# 3.导入模块

import time

start_time = time.time()
for a in range(0, 301):
    for b in range(0, 301):
        c = 30-a-b
        if a**2 + b**2 == c**2:
            print("a, b, c: %d, %d, %d" % (a, b, c))
end_time = time.time()
print(end_time - start_time)
2.5.3 运行结果:

  运行代码后,控制台打印如下图的结果

  这麼一看,发现时间缩短了非要2秒,这一计算时延大大提升。同样正确处理一另一个 问提,将会让我们都都都第二种措施减少了一次for循环嵌套,愿因 计算时延提高了很多很多倍,这一很多很多 算法的重要性。

3. 哪几种是算法

      算法是计算机正确处理信息的本质,将会计算机守护程序运行运行本质上是一另一个 算法来告诉计算机确切的步骤来执行一另一个 指定的任务。一般地,当算法在正确处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备将会某个存储地址供事先再调用。算法是独立趋于稳定的有一种正确处理问提的措施和思想。对于算法而言,实现的编程语言并不重要,重要的是思想。

算法的五大形态:

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

2:输出:算法大概有一另一个 或多个输出

3:有穷性:算法在有限的步骤事先会 自动开始而不用无限循环,而且每一另一个 步骤可不可不还能不能在可接受的时间内完成

4:选用性:算法内的每一步否有选用的含义,不用出现二义性。

5:可行性:算法的每一步否有可行的,也很多很多 说每一步都能执行有限的次数完成。

4. 时间错综复杂度和大O表示法

  上端让我们都都都通过另一个 措施来求出a b c的取值组合,第十个 措施比第一另一个 措施,从时间效果来看,快很多很多,很多很多让我们都都都很容易得出结论,第十个 算法比第一另一个 算法时延要高。这麼算法是通过时间来衡量,虽然 最直观地,让我们都都都从时间上来看一遍算法和算法之间的时延不同。而且,单靠时间是不可靠的,相似,同一另一个 算法,在一另一个 I7的CPU上运行和拿到一另一个 1995年事先的自己PC电脑上运行,这一时间来比较否有点不大概了。很多很多,让我们都都都一般从算法的执行计算数量这一维度去考察算法的时延。执行数量可不可不还能不能这麼理解,上端十个 for循环嵌套的代码,每一行代码否有选用的执行步骤数量,所有代码行的执行步骤数量相加,就得到了这一算法的执行步骤数量。将会每台机器要执行这麼多步骤数量大体相同,很多很多这一执行步骤数量就拿来衡量算法的时延。

  让我们都都都假定计算机执行算法每一另一个 基本操作的时间是固定的一另一个 时间单位,这麼有有几个个基本操作就代表会花费有几个时间单位。对于不同机器而言,确切的单位时间是不同的,而且对于算法进行有几个个基本操作,在规模数量级上说却是相同的。由此可不可不还能不能忽略机器环境影响而客观的反应算法的时间时延。

对于算法的时间时延,让我们都都都可不可不还能不能用“大O记法”来表示。

“大O记法”:对于单调的整数函数f,将会趋于稳定一另一个 整数函数g和实常数c>0,使得对于充分大得n,总有

f(n)<=c*g(n),很多很多 函数g是f得一另一个 渐进函数(忽略常数),记作为f(n)=O(g(n)),也很多很多 说在趋向无穷得

极限意义下,函数f的增长时延收到函数g的约束,亦函数f与函数g的形态相似。

时间错综复杂度:假设趋于稳定函数g,使得算法A正确处理规模为n的问提实例所用时间为T(n)=O(g(n)),则称O(g(n))为算法A

的渐进时间错综复杂度,简称时间错综复杂度,记为T(n)

5. 如可理解“大O记法”

  让我们都都都通过“大O记法”的定义,让我们都都都来计算下上端 a b c这题的第有一种代码实现措施的时间错综复杂度的计算过程。

  让我们都都都根据上端这一图代码对应行来分析(第4到8行代码),先分析每行代码执行步骤数目。

  分析过程:

  第4行:a的取值范围是0到30,很多很多这一for循环要执行30次

  第5行:b的取值范围是0到30,很多很多这一for循环要执行30次

  第6行:c的取值范围是0到30,很多很多这一for循环要执行30次

  第7行:将会不细分步骤,第7和第八两行当作另一个 步骤,将会细分,a + b + c是一另一个 步骤, 判断a + b + c ==30是一另一个 步骤,a**2是一另一个 步骤,很多很多细分,第七行趋于稳定须要执行 8个步骤数目。

  原先,让我们都都都把每一行代码须要执行步骤次数计算出来是

  T = 30 * 30 * 30 * 8

  简写成 T = 8*30^3

  将会,这里把30改成n, 把这一问提规模扩大,这一算法的时间错综复杂度可不可不还能不能写成

  T(n)= 8*n^3

  让我们都都都在计算时间错综复杂度的事先,只关注大头部分,会加上旁支末节部分,一般让我们都都都可不可不还能不能原先认为 n^3和30*n^3是等价,很多很多让我们都都都上端文章开头写的第有一种枚举法的时间错综复杂度是 O(n^3)。

  根据这一时间错综复杂度计算原则,让我们都都都计算第二种算法的时间错综复杂度为O(n^2),这一比第一另一个 时延要高,当然将会时间错综复杂度为n^1,这麼这一算法时延就更高。

6.小结

  好了,今天的分享就到这里吧!!!谢谢各位的耐心阅读。有问提加群交流讨论!!!

您的肯定很多很多 我进步的动力。将会你感觉还不错,就请鼓励一下吧!记得随手点波  推荐  并不忘记哦!!!

别忘了点 推荐 留下您来过的痕迹