企业门户网站的建设与实现,长沙商城网站建设,浙江网架公司,中国建设传媒网官网最近下班一直在学习和总结Python#xff0c;最近在整理数据结构和算法这方面的知识#xff0c;虽然大学的时候也学过数据结构(c语言版本)#xff0c;但是工作这几年一直在做前端所以#xff0c;这方面的知识也忘了差不多#xff0c;所以就想整理一下#xff0c;方便以后自…最近下班一直在学习和总结Python最近在整理数据结构和算法这方面的知识虽然大学的时候也学过数据结构(c语言版本)但是工作这几年一直在做前端所以这方面的知识也忘了差不多所以就想整理一下方便以后自己复习。
下面会说几段代码是想说一下几个概念1大O表示法它主要是用来表示算法效率的一个衡量方法也叫时间复杂度的表示方法。2 算法的特征。3Python内置性能分析。
我们先看一道题 “如果 abc1000且 a^2b^2c^2a,b,c 为自然数如何求出所有a、b、c可能的组合?”
相信大家再看到这个题的时候一定有自己的思路下面是第一种方法。
import timestart_time time.time()
for a in range(1001):for b in range(1001):for c in range(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(time: %d%(end_time - start_time))
print(finished)
我们打印一下结果看计算出这个答案需要的时间。一共是 208秒
a, b, c : 0, 500, 500
a, b, c : 200, 375, 425
a, b, c : 375, 200, 425
a, b, c : 500, 0, 500
time: 208
finished
算法的概念是算法是计算机处理信息的本质因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个任务。简单来说算法是告诉计算机第一步干什么。第二步干什么....然后就任务完成OK。
算法是独立存在的一种解决问题的方法和思想。
比如说上面这个问题在JavaScript语言里面实现的语法就不一样了但是解决这个问题的思路是一样的。对于算法而言实现的语言并不重要重要的是思想。 算法的五大特性了解 1、输入算法具有0个或者多个输入。 2、输出算法至少有1个或者多个输出。算法就是结果问题解决问题后总要有个结果吧 3、又穷性算法在有限的步骤之后会自动结束而不会无限循环。 4、确定性算法中的每一步都有确定的含义不会出现二义性 5、可行性算法的每一步都是可行的。
下面是另外一种方法实现上述问题。
import timestart_time time.time()
for a in range(1001):for b in range(1001):c 1000 - a - bif a**2 b**2 c**2:print(a, b, c: %d, %d, %d%(a,b, c))end_time time.time()print(time: %d%(end_time - start_time))
print(finished)
我们来看一下结果和执行的时间。
a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500
time: 1
finished
可以看出算出来的答案和第一种方法一样但是时间确实相差很大。第一次是208秒第二次是1秒相信大家一下就能看出两个算法的优劣了。
大家看到这个执行时间会有什么想法呢我的想法是第二个算法的效率真高这两个算法不同那么算法的效率怎么衡量呢
我们最直观的感觉是执行时间比如上面两个算法200多秒和1秒的差距还是挺大的。所以我们可以直观的得出一个结论“实现算法程序的执行时间可以反映出算法的效率即算法的优劣“。
但是我们单看从执行时间来判断算法的优劣这样可信吗
假设我们将第二次尝试的算法程序运行在一台配置古老性能低下的计算机中情况会如何很可能运行的时间并不会比在我们的电脑中运行算法一的214.583347秒快多少。
单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的 程序的运行离不开计算机环境包括硬件和操作系统这些客观原因会影响程序运行的速度并反应在程序的执行时间上。 为了客观的反映出算法的优劣提出了时间复杂度与“大O记法”。
我们先看一下 大O表示法的概念。
“大O记法对于单调的整数函数f,如果存在一个整数函数g和实常数c0,使得对于充分大的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)
我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位那么有多少个基本操作就会花费多少时间单位。虽然对于不同的机器环境而言确切的单位时间是不同的但是对于算法进行多少个基本操作即花费的时间单位在规模数量级却是相同的由此可以忽略机器环境的影响而客观的反应算法的时间效率。 简单来说 就是基本操作的数量。 我们先看第一个算法这个算法的操作的基本数量,对于一些加减乘除赋值来说每一都算一个 步骤 1000 * 1000 * 1000 * 9 如果有 n 个话 n * n *n *9 n^3 * 9 我们看 第二个算法 这个算法的步骤 1000 * 1000 * 9 如果有n 个的话 n *n * 9 n^2 * 9
我们主要关注算法的最坏情况亦即最坏时间复杂度
算法分析
01-demo.py 的T(n) O(n*n*n) O(N^3)
02-demo.py 的T(n) O(n*n) O(N^2)
由此可见第二种算法要比第一种算法的时间复杂度好多了。
常见时间复杂度之间的关系
O(1) O(log*n) O(n) O(n*log*n) O(n^2) O(n^3) O(2^n) O(n!) O(n^n)
