Python 算法分析

Python 算法分析详细操作教程

算法分析

可以在实施之前和实施之后的两个不同阶段分析算法的效率。他们是以下-

先验分析 -这是算法的理论分析。通过假设所有其他因素（例如处理器速度）是恒定的，并且对实现没有影响，来衡量算法的效率。
后验分析 -这是对算法的经验分析。所选算法是使用编程语言实现的。然后在目标计算机上执行此操作。在此分析中，收集了诸如运行时间和所需空间之类的实际统计信息。

算法复杂度

假设X是一种算法，n是输入数据的大小，算法X使用的时间和空间是决定X效率的两个主要因素。

时间因数 -时间是通过计算关键操作的数量（例如排序算法中的比较）来衡量的。
空间系数 -通过计算算法所需的最大存储空间来测量空间。

所述算法的复杂性F（N）给出的运行时间和/或在以下方面由该算法所需的存储空间Ñ作为输入数据的大小。

空间复杂度

算法的空间复杂度表示算法在其生命周期中所需的存储空间量。算法所需的空间等于以下两个组成部分的总和-

固定部分，是存储某些数据和变量所需的空间，与问题的大小无关。例如，使用的简单变量和常量，程序大小等。
可变部分是变量所需的空间，其大小取决于问题的大小。例如，动态内存分配，递归堆栈空间等。

任何算法P的空间复杂度S（P）是S（P）= C + SP（I），其中C是算法的固定部分，而S（I）是算法的可变部分，具体取决于实例特征I。是一个简单的例子，试图解释这个概念-

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
Algorithm: SUM(A, B) 
 Step 1 - START 
 Step 2 - C ← A + B + 10 
 Step 3 - Stop

在这里，我们有三个变量A，B和C和一个常数。因此，S（P）= 1 +3。现在，空间取决于给定变量和常量类型的数据类型，并且空间将相应地相乘。

时间复杂度

算法的时间复杂度表示算法运行完成所需的时间。时间要求可以定义为数值函数T（n），其中T（n）可以作为步数进行测量，前提是每一步都消耗恒定的时间。

例如，两个n位整数相加需要n步。因此，总的计算时间为T（n）= c * n，其中c是两个位相加所花费的时间。在这里，我们观察到T（n）随着输入大小的增加而线性增长。

Python 简介

Python 算法类型