Python Data Structure 简明教程

Python - Algorithm Analysis

算法的效率可以在两个不同的阶段进行分析，在实现之前和实现之后。它们如下所示 −

Efficiency of an algorithm can be analyzed at two different stages, before implementation and after implementation. They are the following −

  1. A Priori Analysis − This is a theoretical analysis of an algorithm. Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation.

  2. A Posterior Analysis − This is an empirical analysis of an algorithm. The selected algorithm is implemented using programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.

Algorithm Complexity

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

Suppose X is an algorithm and n is the size of input data, the time and space used by the algorithm X are the two main factors, which decide the efficiency of X.

  1. Time Factor − Time is measured by counting the number of key operations such as comparisons in the sorting algorithm.

  2. Space Factor − Space is measured by counting the maximum memory space required by the algorithm.

算法 f(n) 的复杂度根据输入数据的规模 n 给出了算法的运行时间和/或存储空间要求。

The complexity of an algorithm f(n) gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data.

Space Complexity

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

Space complexity of an algorithm represents the amount of memory space required by the algorithm in its life cycle. The space required by an algorithm is equal to the sum of the following two components −

  1. A fixed part that is a space required to store certain data and variables, that are independent of the size of the problem. For example, simple variables and constants used, program size, etc.

  2. A variable part is a space required by variables, whose size depends on the size of the problem. For example, dynamic memory allocation, recursion stack space, etc.

任何算法 P 的空间复杂度 S(P) 为 S(P) = C + SP(I)，其中 C 是固定部分，S(I) 是算法的可变部分，它取决于实例特征 I。以下是一个尝试解释该概念的简单示例 −

Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed part and S(I) is the variable part of the algorithm, which depends on instance characteristic I. Following is a simple example that tries to explain the concept −

Algorithm: SUM(A, B)

Algorithm: SUM(A, B)

步骤 1 − 开始

Step 1 − START

步骤 2 − C ← A + B + 10

Step 2 − C ← A + B + 10

步骤 3 − 停止

Step 3 − Stop

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

Here we have three variables A, B, and C and one constant. Hence S(P) = 1 + 3. Now, space depends on data types of given variables and constant types and it will be multiplied accordingly.

Time Complexity

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

Time complexity of an algorithm represents the amount of time required by the algorithm to run to completion. Time requirements can be defined as a numerical function T(n), where T(n) can be measured as the number of steps, provided each step consumes constant time.

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

For example, addition of two n-bit integers takes n steps. Consequently, the total computational time is T(n) = c ∗ n, where c is the time taken for the addition of two bits. Here, we observe that T(n) grows linearly as the input size increases.