Python 算法分析

算法分析

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

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

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

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

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

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 分而治之