大发10分彩软件_《从入门到放弃》数据结构和算法 1

  • 时间:
  • 浏览:2

1. 简介 

  最近机会快过年了,都是很忙碌了,人心浮动,太久都请假了,现在终于有时间来系统学习下和恶补一下常见数据社会形态和算法的知识,太久,还是通过记录笔记倒入博客的最好的土措施来督促我该人学习。一齐和小伙伴们分享一下学习心得与体会。算法对于太久守护守护进程员都接触只有的,何况是一1个测试人员。某些面试过程中,多有哪几个少都是算法题的面试。太久,学习算法,短期来看是为了跳槽准备,长期来看,是锻炼一一两我该人防止间题的思路的提升的一1个途径。

2. 算法的引入

  来看一1个间题:机会 a+b+c = 4000, 且 a^2 + b^2 = c^2(勾股定理),如何求出所有a b c的组合。

2.1 间题分析:

  顶端告诉一1个条件,从数学淬硬层 来说,顶端有1个未知数,只有一1个表达式条件,亲们第一反应是转去掉 二元二次方程来解答。这里亲们是计算机通过代码来防止间题。字面意思否则 a的取值范围是0到4000, b的取值范围是0到4000, c的取值范围是0到4000, 某些去掉 题目的一1个表达式条件,利用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, 4001):
    for b in range(0, 4001):
        for c in range(0, 4001):
            if a + b + c == 4000 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 运行结果:

  人太好顶端代码思路也是用到了一1个最好的土措施,叫枚举法,否则一1个一1个列出来去尝试,不行,换下一1个值继续去匹配。

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

  也否则差太久花费三分钟(117秒多),找出了符合条件的a b c的有一种取值组合。机会没人 计算机,人也是可不还可不可否根据你什儿 思路,一步一步去算,只不过时间更是我没人了乎 有多慢。你什儿 时间开销,亲们很不满意,对用户来说,还是太慢了。有没人 那些最好的土措施提升以下计算速度。

2.5 优化顶端代码:

  根据数学知识,亲们用代码实现二元二次方程的思路,c = 4000 - 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, 4001):
    for b in range(0, 4001):
        c = 4000-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秒,你什儿 计算速度大大提升。同样防止一1个间题,机会亲们第二种最好的土措施减少了一次for循环嵌套,由于计算速度提高了太久倍,你什儿 否则算法的重要性。

3. 那些是算法

      算法是计算机防止信息的本质,机会计算机守护守护进程本质上是一1个算法来告诉计算机确切的步骤来执行一1个指定的任务。一般地,当算法在防止信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备机会某个存储地址供愿意再调用。算法是独立所处的有一种防止间题的最好的土措施和思想。对于算法而言,实现的编程语言暂且重要,重要的是思想。

算法的五大社会形态:

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

2:输出:算法为宜有一1个或多个输出

3:有穷性:算法在有限的步骤从过后 自动结束而不想无限循环,某些每一1个步骤可不还可不可否在可接受的时间内完成

4:取舍性:算法内的每一步都是取舍的含义,不想老出二义性。

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

4. 时间多样化度和大O表示法

  顶端亲们通过一1个最好的土措施来求出a b c的取值组合,第1个最好的土措施比第一1个最好的土措施,从时间效果来看,快太久,太久亲们很容易得出结论,第1个算法比第一1个算法速度要高。没人 算法是通过时间来衡量,人太好最直观地,亲们从时间上来看后算法和算法之间的速度不同。某些,单靠时间是不可靠的,同类,同一1个算法,在一1个I7的CPU上运行和拿到一1个1995年愿意的我该人PC电脑上运行,你什儿 时间来比较都是得劲不为宜了。太久,亲们一般从算法的执行计算数量你什儿 维度去考察算法的速度。执行数量可不还可不可否没人 理解,顶端1个for循环嵌套的代码,每一行代码都是取舍的执行步骤数量,所有代码行的执行步骤数量相加,就得到了你什儿 算法的执行步骤数量。机会每台机器要执行没人 多步骤数量大体相同,太久你什儿 执行步骤数量就拿来衡量算法的速度。

  亲们假定计算机执行算法每一1个基本操作的时间是固定的一1个时间单位,没人 有有哪几个个基本操作就代表会花费有哪几个时间单位。对于不同机器而言,确切的单位时间是不同的,某些对于算法进行有哪几个个基本操作,在规模数量级上说却是相同的。由此可不还可不可否忽略机器环境影响而客观的反应算法的时间速度。

对于算法的时间速度,亲们可不还可不可否用“大O记法”来表示。

“大O记法”:对于单调的整数函数f,机会所处一1个整数函数g和实常数c>0,使得对于充分大得n,总有

f(n)<=c*g(n),否则函数g是f得一1个渐进函数(忽略常数),记作为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到4000,太久你什儿 for循环要执行4000次

  第5行:b的取值范围是0到4000,太久你什儿 for循环要执行4000次

  第6行:c的取值范围是0到4000,太久你什儿 for循环要执行4000次

  第7行:机会不细分步骤,第7和第八两行当作一1个步骤,机会细分,a + b + c是一1个步骤, 判断a + b + c ==4000是一1个步骤,a**2是一1个步骤,太久细分,第七行所处只有执行 8个步骤数目。

  从前,亲们把每一行代码只有执行步骤次数计算出来是

  T = 4000 * 4000 * 4000 * 8

  简写成 T = 8*4000^3

  机会,这里把4000改成n, 把你什儿 间题规模扩大,你什儿 算法的时间多样化度可不还可不可否写成

  T(n)= 8*n^3

  亲们在计算时间多样化度的愿意,只关注大头偏离 ,会去掉 旁支末节偏离 ,一般亲们可不还可不可否从前认为 n^3和4000*n^3是等价,太久亲们顶端文章开头写的第有一种枚举法的时间多样化度是 O(n^3)。

  根据你什儿 时间多样化度计算原则,亲们计算第二种算法的时间多样化度为O(n^2),你什儿 比第一1个速度要高,当然机会时间多样化度为n^1,没人 你什儿 算法速度就更高。

6.小结

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

您的肯定否则进步的动力。机会你感觉还不错,就请鼓励一下吧!记得随手点波  推荐  暂且忘记哦!!!

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