数据与算法绪论

本部分主要解决以下几个问题：

• 什么是数据结构？
• 什么是算法？如何进行算法分析？
• 数据结构和算法之间具有怎样的关系？

什么是数据

• 数据(data)是描述客观事物且能被计算加工处理的数值、字符等符号的总称。
• 数据元素(data element)是数据的基本单位，是数据集合中的一个个体。在计算机程序中通常作为一个整体来考虑和处理。它可以由一个或多个数据项data item组成(据此数据元素分为原子元素和结构元素) 。数据项是数据的最小单位，是”不可再分的”。
• 数据对象(data object)是性质相同的数据元素的集合，它是数据的一个子集。

什么是数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一个二元组1，记为:data_structrue=(D,S);

• D为数据元素的集合
• S是D上关系的集合。

数据元素相互之间的关系称为结构(structure)

[1] 二元组是数学中的一个概念，表示由两个元素组成的有序对。它是集合论和数理逻辑中的基本概念，常用于描述和表示两个对象之间的关系或组合。

数据结构包括数据元素的逻辑结构、存储结构和相适应的数据运算三个方面的内容。

逻辑结构

是指数据之间的逻辑关系。它与计算机无关，一般概念的数据结构是指数据的逻辑结构。 数据的逻辑结构通常有以下四种：

• 集合结构：数据元素彼此之间 没有直接关系，只有“属于同 一集合”的联系。
• 线性结构：数据元素之间存在一对一的关系。
• 树形结构：数据元素之间存在一对多的关系。
• 图状结构或网状结构：数据元素之间存在多对多的关系。

存储结构

指数据元素及其关系在计算机存储器中的表示（映像）。其主要内容是指在存储空间中使用一个存储结点来存储一个数据元素；在存储空间中建立各存储结点的关联来表示数据元素之间的逻辑关系。

数据的存储结构有以下4种基本方式:

• 顺序存储：所有的存储结点相继存储在连续的存储区内。用存储结点间的位置关系表示数据元素之间的逻辑关系。
• 链式存储：每一个存储结点不仅含一个数据元素，还包括指针。每一个指针指向一个与本结点有逻辑关系的结点，即用指针表示逻辑关系。
• 索引存储：通常用于存储线性结构时，另附设索引表，索引表项的一般形式(关键字,地址)，用于指示一个数据元素或一部分数据元素。
• 散列存储：数据元素按散列(Hash)函数确定存储位置。

一种逻辑结构可映象成不同的存储结构：顺序存储结构和非顺序存储结构。

数据运算

数据运算指在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。

常用的基本运算：

• 建立数据结构：使一个数据结构可用并将其初始化。
• 检索数据元素：从结构中找出满足某种条件的元素。
• 插入数据元素：在结构中的某个指定位置增加一个元素。
• 删除数据元素：撤消结构中指定位置的元素。
• 更新数据元素：修改结构中某指定位置元素的内容。
• 求长：计算结构中的数据元素个数。
• 读取运算 ：读出结构中指定位置元素的内容。
• 排序运算：使结构中的元素递增或递减有序。

什么是数据类型

数据类型(data type)是一个值的集合和定义在此集合上的一组操作。

抽象数据类型(abstract data type)数据类型概念的引伸。指一个数学模型以及在其上定义的操作集合。其特点在于将它的使用和实现分离，提高软件复用程度。抽象数据类型可以用以下三元组表示： ADT=（D，R，P）

下面是对三个元素的解释：

• D（Data）：ADT中的数据部分，它定义了数据对象的集合以及这些对象之间的关系。D描述了ADT中数据的抽象特性
• 数据类型
• 数据属性
• 数据约束
• ......
• R（Relationship）：ADT中的关系部分，R描述了数据对象之间的关系和操作。R描述了数据对象之间的逻辑关联
• 数据存取
• 数据修改
• 数据操作
• ......
• P（Property）：ADT中的操作部分，它定义了对数据对象进行操作的属性和约束。P描述了对数据对象进行操作的规则和行为
• 数据创建
• 数据销毁
• 数据查询
• 数据修改
• ......

算法

什么是算法

算法是指解决问题或执行任务的一系列明确步骤的有序集合。它是一个用来描述计算过程的精确而又抽象的指导方针。算法可以被看作是一种计算模型，它描述了如何在输入数据上进行一系列的操作，以产生所需的输出结果。

算法具有以下特点：

• 明确性：算法必须具有明确的步骤，每个步骤都要清晰、精确地描述，不会产生歧义。算法的每个步骤都应该能够被理解和执行。
• 有限性(有穷性)：算法必须在有限的时间内完成。即使在处理大规模数据时，算法也应该能够在有限的时间内终止。
• 输入：算法接受输入数据，这些数据可以是预先定义的、用户提供的或通过其他方式获取的。输入数据是算法执行的基础。
• 输出：算法产生输出结果，这些结果可以是计算得到的值、修改后的数据、打印的信息等，根据具体问题的要求而定。
• 可行性：算法的每个步骤都应该是可行的，即每个步骤都可以在有限的时间和资源内执行。

算法分析

算法分析主要是指对算法效率的分析。算法效率包括两个方面：时间效率和空间效率。

• 时间效率：指出了正在讨论的算法运行得有多快。
• 空间效率：则关心算法需要的额外空间。

时间复杂度

渐近时间复杂性是一种用来描述算法时间复杂度的分析方法，它关注算法在输入规模趋于无穷大时的增长趋势。它使用大O符号（O）来表示算法的渐近上界，即算法在最坏情况下的时间复杂度。

下面给出O的形式化定义：

这个定义可以解释为：对于足够大的输入规模n，函数f(n)的增长速度不会超过函数g(n)的增长速度乘以一个常数c。这里的常数c可以理解为一个界限，表示函数f(n)的增长速度在最坏情况下不会超过函数g(n)的增长速度的c倍。

常见渐近时间复杂度

常用的时间复杂度所耗费的时间从大到小依次是：

O(1) < O(log2n) <O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2) < O(n!) <O(n)

嵌套和并列

在分析算法的时间复杂度时，常见的情况是存在嵌套和并列的时间复杂度。

• 时间复杂度的嵌套（Nested Time Complexity）：当一个算法中的某个操作（如循环、递归等）内部包含另一个操作时，将内外两个循环的时间复杂度相乘来得到总体的时间复杂度:O(f(n) * g(n))
• 时间复杂度的并列（Parallel Time Complexity）：当一个算法的不同部分在同一层级并列执行时，它们的时间复杂度可以被认为是相互独立的:O(max(f(n), g(n)))

总结起来，嵌套相乘,并列取大。

实例分析

#include <stdio.h>
//O(1)
int constantTime(int n)
{
    int x = 5;
    int y = 10;
    int z = x + y;
    return z;
}
//O(n)
void linearTime(int n) 
{
    for (int i = 0; i < n; i++) 
    {
        printf("%d ", i);
    }
}
//O(logn)
void logarithmicTime(int n) 
{
    int i = 1;
    while (i < n) 
    {
        printf("%d ", i);
        i *= 2;
    }
}
//O(n^2)
void quadraticTime(int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++) 
        {
            printf("%d ", i + j);
        }
    }
}
//O(2^n)
int exponentialTime(int n) 
{
    if (n <= 1) 
    {
        return n;
    }
    else 
    {
        return exponentialTime(n - 1) + exponentialTime(n - 2);
    }
}
int main()
{
    return 0;
}

空间复杂度

空间复杂度是衡量算法在执行过程中所需的额外空间的度量。它表示算法所使用的额外空间随着输入规模的增长而变化的情况。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。常见空间复杂度同上

影响空间复杂度的因素主要有以下三点:

• 算法输入输出数据所占用的存储空间(函数参数)
• 存储算法本身所占用的存储空间(算法书写长短)
• 算法执行过程中临时占用的存储空间(额外使用内存)

实例分析

#include <stdio.h>
//O(1)
void print() 
{
    printf("O(1)\n");
}
//O(n)
int sum_arr(int arr[],int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++) 
    {
        sum += arr[i];
    }
    return sum;
}
//O(logn)
int binarySearch(int arr[], int low, int high, int target)
{
    if (low > high)
        return -1;
    int mid = (low + high) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return binarySearch(arr, low, mid - 1, target);
    else
        return binarySearch(arr, mid + 1, high, target);
}
//O(n^2)
void print_matrix(int **matrix,int rows,int cols)
{
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            printf("%d", matrix[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    return 0;
}

经典算法时间复杂度

排序算法

搜索算法

图算法

字符串匹配算法

其他常用算法

相关

如果阁下正好在学习C/C++，看文章比较无聊，不妨关注下关注下小编的视频教程，通俗易懂，深入浅出，一个视频只讲一个知识点。视频不深奥，不需要钻研，在公交、在地铁、在厕所都可以观看，随时随地涨姿势。