Data Structures Algorithms 简明教程

Data Structures - Algorithms Basics

算法是一个循序渐进的过程，它定义了一组按特定顺序执行的指令，以获得所需的输出。算法通常独立于底层语言创建，即算法可以在不止一种编程语言中实现。

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

从数据结构的角度来看，以下是一些重要的算法类别 -

From the data structure point of view, following are some important categories of algorithms −

  1. Search − Algorithm to search an item in a data structure.

  2. Sort − Algorithm to sort items in a certain order.

  3. Insert − Algorithm to insert item in a data structure.

  4. Update − Algorithm to update an existing item in a data structure.

  5. Delete − Algorithm to delete an existing item from a data structure.

Characteristics of an Algorithm

并非所有程序都可以称为算法。算法应具有以下特征 -

Not all procedures can be called an algorithm. An algorithm should have the following characteristics −

  1. Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning.

  2. Input − An algorithm should have 0 or more well-defined inputs.

  3. Output − An algorithm should have 1 or more well-defined outputs, and should match the desired output.

  4. Finiteness − Algorithms must terminate after a finite number of steps.

  5. Feasibility − Should be feasible with the available resources.

  6. Independent − An algorithm should have step-by-step directions, which should be independent of any programming code.

How to Write an Algorithm?

对于编写算法，没有明确定义的标准。相反，它取决于问题和资源。算法永远不会被编写来支持特定的编程代码。

There are no well-defined standards for writing algorithms. Rather, it is problem and resource dependent. Algorithms are never written to support a particular programming code.

正如我们所知，所有编程语言都共享基础代码构造，如循环（do、for、while）、流程控制（if-else）等。这些通用构造可用于编写算法。

As we know that all programming languages share basic code constructs like loops (do, for, while), flow-control (if-else), etc. These common constructs can be used to write an algorithm.

我们按部就班编写算法，但并不总是如此。算法编写是一个过程，在问题域定义明确后执行。也就是说，我们应该了解问题域，并针对该问题域设计解决方案。

We write algorithms in a step-by-step manner, but it is not always the case. Algorithm writing is a process and is executed after the problem domain is well-defined. That is, we should know the problem domain, for which we are designing a solution.

Example

我们尝试通过示例来学习算法编写。

Let’s try to learn algorithm-writing by using an example.

Problem − 设计一种算法来对两个数字进行加法并显示结果。

Problem − Design an algorithm to add two numbers and display the result.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

算法告诉程序员如何对程序进行编码。或者，算法可以写成 −

Algorithms tell the programmers how to code the program. Alternatively, the algorithm can be written as −

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

在算法的设计和分析中，通常使用第二种方法来描述算法。这使得分析员能够轻松地分析算法，而忽略所有不需要的定义。他可以观察正在使用什么操作以及流程如何进行。

In design and analysis of algorithms, usually the second method is used to describe an algorithm. It makes it easy for the analyst to analyze the algorithm ignoring all unwanted definitions. He can observe what operations are being used and how the process is flowing.

编写 step numbers 是可选的。

Writing step numbers, is optional.

我们设计了一个算法来解决给定问题。一个问题可以用多种方法解决。

We design an algorithm to get a solution of a given problem. A problem can be solved in more than one ways.

algorithm analysis

因此，可以为给定的问题导出许多求解算法。下一步是分析那些建议的求解算法并执行最适合的解决方案。

Hence, many solution algorithms can be derived for a given problem. The next step is to analyze those proposed solution algorithms and implement the best suitable solution.

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.

我们将了解先验算法分析。算法分析处理所涉及的各种操作的执行或运行时间。操作的运行时间可以定义为每个操作执行的计算机指令数量。

We shall learn about a priori algorithm analysis. Algorithm analysis deals with the execution or running time of various operations involved. The running time of an operation can be defined as the number of computer instructions executed per operation.

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)
Step 1 − START
Step 2 − C ← A + B + 10
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.