设计与分析简介

算法是解决执行计算、数据处理和自动推理任务的问题的一组操作步骤。算法是一种可以在有限的时间和空间内表达的有效方法。

算法是以非常简单且有效的方式表示特定问题的解决方案的最佳方式。如果我们有针对特定问题的算法，那么我们可以用任何编程语言来实现它，这意味着该算法独立于任何编程语言。

算法设计

算法设计的重要方面包括创建有效的算法，以使用最少的时间和空间以有效的方式解决问题。

为了解决问题，可以采用不同的方法。其中一些方法在时间消耗方面可能是高效的，而其他方法可能是内存效率高的。然而，必须记住，时间消耗和内存使用不能同时优化。如果我们需要算法在更短的时间内运行，我们就必须投资更多的内存，如果我们需要算法在更少的内存下运行，我们就需要更多的时间。

算法分析

问题发展步骤

解决计算问题涉及以下步骤。

  • 问题定义
  • 模型开发
  • 算法规范
  • 设计算法
  • 检查算法的正确性
  • 算法分析
  • 算法的实现
  • 程序测试
  • 文档

如何编写算法？

编写算法没有明确的标准。相反，它依赖于问题和资源。算法从来都不是为了支持特定的编程代码而编写的。

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

我们以一步一步的方式编写算法，但情况并非总是如此。算法编写是一个过程，是在问题域明确之后执行的。也就是说，我们应该了解我们正在设计解决方案的问题领域。

例子

让我们尝试通过一个例子来学习算法编写。

问题- 设计一个算法来添加两个数字并显示结果。

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

算法告诉程序员如何编写程序。或者，该算法可以写为 -

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

在算法的设计和分析中，通常采用第二种方法来描述算法。它使分析人员可以轻松分析算法，忽略所有不需要的定义。他可以观察正在使用哪些操作以及流程如何流动。

算法特点

并不是所有的过程都可以称为算法。算法应具有以下特征 -

  • 明确- 算法应该清晰且明确。它的每个步骤（或阶段）及其输入/输出都应该清晰，并且必须仅产生一个含义。

  • 输入- 算法应该有 0 个或多个明确定义的输入。

  • 输出- 算法应该有 1 个或多个明确定义的输出，并且应该与所需的输出相匹配。

  • 有限性- 算法必须在有限数量的步骤后终止。

  • 可行性- 在可用资源下应该可行。

  • 独立- 算法应该有逐步的方向，它应该独立于任何编程代码。

伪代码

伪代码给出了算法的高级描述，没有与纯文本相关的歧义，而且也不需要知道特定编程语言的语法。

通过使用伪代码将算法表示为一组可以计算的基本操作，可以以更通用的方式估计运行时间。

算法和伪代码之间的区别

算法是具有一些特定特征的形式定义，描述了一个过程，可以由图灵完备的计算机执行以执行特定任务。一般来说，“算法”这个词可以用来描述计算机科学中的任何高级任务。

另一方面，伪代码是对算法的非正式且（通常是基本的）人类可读的描述，留下了许多细粒度的细节。编写伪代码没有风格限制，其唯一目标是用自然语言以更加现实的方式描述算法的高级步骤。

例如，以下是插入排序的算法。

Algorithm: Insertion-Sort 
Input: A list L of integers of length n  
Output: A sorted list L1 containing those integers present in L 
Step 1: Keep a sorted list L1 which starts off empty  
Step 2: Perform Step 3 for each element in the original list L  
Step 3: Insert it into the correct position in the sorted list L1.  
Step 4: Return the sorted list 
Step 5: Stop

这是一个伪代码，描述了如何以更现实的方式描述算法插入排序中的上述高级抽象过程。

for i <- 1 to length(A) 
   x <- A[i] 
   j <- i 
   while j > 0 and A[j-1] > x 
      A[j] <- A[j-1] 
      j <- j - 1 
   A[j] <- x

在本教程中，算法将以伪代码的形式呈现，这在许多方面与 C、C++、Java、Python 和其他编程语言类似。

例子

C C++ Java Python 
#include <stdio.h>
void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        // Move elements of arr[0..i-1] that are greater than key,
        // to one position ahead of their current position.
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // Insert the current element (key) in the correct position.
    }
}
int main() {
    int arr[] = {6, 4, 26, 14, 33, 64, 46};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

输出

Sorted array: 4 6 14 26 33 46 64 

#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // Move elements of arr[0..i-1] that are greater than key,
        // to one position ahead of their current position.
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // Insert the current element (key) in the correct position.
    }
}
int main() {
    int arr[] = {6, 4, 26, 14, 33, 64, 46};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

输出

Sorted array: 4 6 14 26 33 46 64 

import java.util.Arrays;
public class InsertionSort {
    public static void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // Move elements of arr[0..i-1] that are greater than key,
            // to one position ahead of their current position.
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key; // Insert the current element (key) in the correct position.
        }
    }
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

输出

Sorted array: [11, 12, 22, 25, 34, 64, 90]

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        # Move elements of arr[0..i-1] that are greater than key,
        # to one position ahead of their current position.
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # Insert the current element (key) in the correct position.

arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("Sorted array:", arr)

输出

Sorted array: [11, 12, 22, 25, 34, 64, 90]