Python - 摊销分析

分期分析包括估算程序中操作序列的运行时间,而不考虑输入值中数据分布的范围。一个简单的例子是在排序列表中查找值比在未排序列表中快。如果列表已经排序,则数据分布的方式无关紧要。但是,当然,列表的长度会影响算法,因为它决定算法必须经过的步骤才能获得最终结果。

因此,我们看到,如果获得排序列表的单个步骤的初始成本很高,则后续找到元素的步骤的成本变得相当低。因此,摊销分析有助于我们找到一系列操作的最坏情况运行时间的限制。分摊分析有三种方法。

  • 会计方法 - 这涉及为每个执行的操作分配成本。 如果实际操作比指定的时间更快结束,那么分析中会积累一些积极的信用。在相反的情况下,它将是负信贷。为了跟踪这些累计学分,我们使用堆栈或树形数据结构。早期进行的操作(如清单分类)具有较高的摊销成本,但随着积累的信用被利用,较晚的操作具有较低的摊销成本。所以摊余成本是实际成本的上限。

  • 潜在方法 - 在这种方法中,将保存的信用作为数据结构状态的数学函数用于将来的操作。 数学函数的评估和摊销成本应该是相等的。因此,当实际成本高于摊销成本时,潜在价值会下降,并且将用于未来昂贵的运营。

  • 综合分析 - 在这种方法中,我们估计n步骤总成本的上限。 摊销成本是总成本和步骤数(n)的简单划分。

推荐教程

Python 2.7.X 手册

Python 2.7基础语法、实例讲解

Python实用手册

Python 实战演练、轻松入门

PySpark教程

Apache Spark是一个闪电般快速的实时处理框架

Seaborn教程

Seaborn是Python中的可视化库

Flask教程

Flask是一个用Python编写的Web应用程序框架

Django教程

Django是一个Web开发框架

Web2py教程

Web2py被定义为一个免费的开源Web开发框架

Scrapy教程

Scrapy是一个用Python编写的快速,开源的网页爬虫框架

Python3 教程

常被称为Python 3000,或简称Py3k

Python数据结构

算法是一步一步的指令集来处理特定用途的数据