Python教程

当前位置:小码王 > 学习教程 > Python教程

Python编程之算法复杂度
导读:python编程是目前新出来的一门语言,如今也非常的热门,也是少儿编程的一门学科,可以通过python来培养孩子对编程的兴趣,培养孩子的思维,有时候也可以做一些复杂的程序,今天就让南京小码王少儿编程培训机构老师分享,Pyt

  python编程是目前新出来的一门语言,如今也非常的热门,也是少儿编程的一门学科,可以通过python来培养孩子对编程的兴趣,培养孩子的思维,有时候也可以做一些复杂的程序,今天就让南京小码王少儿编程培训机构老师分享,Python编程之算法复杂度。


  首先,在我们考虑计算复杂度之间,我们先思考一个问题,运行下面这个函数需要多长时间。

1.png


  我们可以使用一些输入来运行程序并计时,但结果并没有太大的意义,因为这样做的结果依赖于以下几个因素:


  1、运行程序的计算机性能;


  2、计算机上Python系统的效率;


  3、输入值。


  我们可以使用一种更加抽象的时间量度来解决前面两个问题。不再使用毫秒测量时间,而是以程序执行的基本步数为单位进行测量。


  为了简单期间,我们使用随机存取机作为计算模型。在随机存取机中,步数是顺序执行的,每次执行一步,一步指的是一个需要固定时间量的操作,比如将变量绑定到对象、做一次比较、执行一次代数运算或访问内存中的对象。


  既然我们已经使用了一种更抽象的方法来表示时间,下面就解决对输入值的依赖问题。不再用一个独立的数值表示时间复杂度,而是将时间复杂度与输入的规模联系起来。这样,比较两种算法的运行时间如何随着输入规模的增加而增加,即可比较两种算法的效率。


  当然,算法的实际运行时间不仅依赖于输入规模,还依赖于具体的输入值。例如,考虑以下代码中实现的线性搜索算法:

2.png


  假设L是一个包含100万一个元素的列表,我们看一个函数调用linearSearch(L,3)。如果L中的一个元素是3,那么linearSearch几乎会立刻返回True。另一方面,如果3不在L中,那么linearSearch就必须在返回False之前,检查所有100万个元素。


  一般而言,我们需要考虑三种常见的情形:


  1、最佳情形运行时间是在输入最有利的情况下算法的运行时间。也就是说,在给定输入规模的情况下的最短的运行时间。对于linearSearch,最佳情形运行时间与L的大小无关。


  2、最差情形运行时间是在给定输入规模的情况下最长的运行时间。对于linearSearch,最差情形运行时间与L的大小成正比。


  3、平均情形(也被称为期望情形)运行时间是在给定输入规模的情况下的平均运行时间。此外,如果关于输入值的分布有一些先验信息(例如,在90%的情形下,x在L中),也应该将这些信息考虑在内。Python中的工具(函数)与模具(类)


  南京小码王专业从事青少儿编程教育,开设了专门的Python培训班,有丰富的Python教程和专业老师,通过理论结合实践的方式教学,让孩子能更好的掌握Python知识。目前小码王还有0元体验课正在进行中,欢迎大家前来试听体验,感受Python编程的乐趣。