关于程序员:探索数据结构解锁计算世界的密码

✨✨ 欢送大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty‘s blog

前言

随着应用程序变得越来越简单和数据越来越丰盛，几百万、几十亿甚至几百亿的数据就会呈现，而对这么大对数据进行搜寻、插入或者排序等的操作就越来越慢，人们为了解决这些问题，进步对数据的管理效率，提出了一门学科即：数据结构与算法

1. 什么是数据结构

数据结构 (Data Structure) 是计算机存储、组织数据的形式，指相互之间存在一种或多种特定关系的数据元素的汇合。

下标是常见的数据结构:

2. 什么是算法

算法 (Algorithm): 就是定义良好的计算过程，他取一个或一组的值为输出，并产生出一个或一组值作为输入。简略来说算法就是一系列的计算步骤，用来将输出数据转化成输入后果。

算法个别分为：排序，递归与分治，回溯，DP，贪婪，搜索算法

• 算法往往数学密切相关，就如数学题一样，每道数学题都有不同的解法，算法也是同理。

3. 复杂度剖析

3.1 算法评估

咱们在进行算法剖析时，经常须要实现两个指标。一个是找出问题的解决办法，另一个就是找到问题的最优解。而为了找出最优解，咱们就须要从两个维度剖析：

• 工夫效率：算法运行的快慢
• 空间效率：算法所占空间的大小

3.2 评估办法

评估工夫的办法次要分为两种，一种是 试验分析法 ，一种是 实践分析法。

(1) 试验分析法

试验分析法简略来说就是将不同种算法输出同一台电脑，统计工夫的快慢。然而这种办法有两大缺点：

1. 无奈排查试验本身条件与环境的条件的影响：比方同一种算法在不同配置的电脑上的运算速度可能齐全不同，甚至后果齐全相同。咱们很难排查所有状况。
2. 老本太高：同一种算法可能在数据少时体现不显著，在数据多时速率较快

(2) 实践分析法

因为试验分析法的局限性，就有人提出了一种实践测评的办法，就是 渐近复杂度剖析 (asymptotic complexity analysis)，简称 复杂度剖析。

这种办法体现算法运行所需的 工夫（空间）资源与输出数据大小 之间的关系，能无效的反馈算法的优劣。

4. 工夫复杂度与空间复杂度

4.1 工夫复杂度

一个算法 所破费的工夫与其中语句的执行次数 成正比例，算法中的基本操作的执行次数，为算法的工夫复杂度。

为了精确的表述一段代表所需工夫，咱们先假如赋值 (=) 与加号 (+) 所需工夫为 1ns，乘号 (×) 所需工夫为 2ns，打印所需为 3ns。

让咱们计算如下代码所需总工夫：

int main()
{
    int i = 1;//1ns
    int n = 0;//1ns
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {printf("%d", i);//3ns
    }
    return 0;
}

计算工夫如下：

$$
T(n)=1+1+3×n=3n+2
$$

然而实际上统计每一项所需工夫是不事实的，并且因为是实践剖析，当 n—>∞时，其余项皆可疏忽，T(n)的数量级由最高阶决定。所以咱们计算工夫复杂度时，能够简化为两个步骤：

1. 疏忽除最高阶以外的所有项。
2. 疏忽所有系数。

而上述代码工夫能够记为 O(n)，这种办法被称为 大 O 的渐进表示法。如果计算机后果全是常数，则记为 O(1)。

• 并且计算复杂度时，有时候会呈现不同状况的后果，这是应该以最坏的后果思考。

4.2 空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中 长期占用存储空间大小 的量度。空间复杂度的示意也遵循 大 O 的渐进表示法

让咱们计算一下冒泡排序的空间复杂度

// 计算 BubbleSort 的空间复杂度？void BubbleSort(int* a, int n)
{assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {if (a[i - 1] > a[i])
            {Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}

• 通过观察咱们能够看出，冒泡排序并没有开拓多余的空间，所以空间复杂度为 O(1).

5. 复杂度分类

算法的复杂度有几个量级，示意如下：

$$
O(1) < O(log N) < O(N) < O(Nlog N) < O(N 2) < O(2^𝑛) < 𝑂(O!)
$$

• 从左到右复杂度顺次递增，算法的毛病也就越显著

图示如下：

5.1 常数 O(1)阶

常数阶是一种十分疾速的算法，然而在理论利用中十分难实现

以下是一种工夫复杂度与空间复杂度皆为 O(1)的算法：

int main()
{
    int a = 0;
    int b = 1;
    int c = a + b;
    printf("两数之和为 %d\n", c);
    return 9;
}

5.2 对数阶 O(logN)

对数阶是一种比拟快的算法，它个别每次缩小一半的数据。咱们罕用的二分查找算法的工夫复杂度就为 O(logN)

二分查找如下：

int binary_search(int nums[], int size, int target) //nums 是数组，size 是数组的大小，target 是须要查找的值
{
    int left = 0;
    int right = size - 1;    // 定义了 target 在左闭右闭的区间内，[left, right]
    while (left <= right) {// 当 left == right 时，区间 [left, right] 依然无效
        int middle = left + ((right - left) / 2);// 等同于 (left + right) / 2，避免溢出
        if (nums[middle] > target) {right = middle - 1;    //target 在左区间，所以[left, middle - 1]
        } else if (nums[middle] < target) {left = middle + 1;    //target 在右区间，所以[middle + 1, right]
        } else {    // 既不在右边，也不在左边，那就是找到答案了
            return middle;
        }
    }
    // 没有找到目标值
    return -1;
}

空间复杂度为 O(logN)的算法，个别为分治算法

比方用递归实现二分算法：

int binary_search(int ar[], int low, int high, int key)
{if(low > high)// 查找不到
        return -1;
    int mid = (low+high)/2;
    if(key == ar[mid])// 查找到
        return mid;
    else if(key < ar[mid])
        return Search(ar,low,mid-1,key);
    else
        return Search(ar,mid+1,high,key);
}

每一次执行递归都会对应开拓一个空间，也被称为 栈帧。

5.3 线性阶 O(N)

线性阶算法，工夫复杂度与空间复杂度随着数量平均变动。

遍历数组或者链表是常见的线性阶算法，以下为工夫复杂度为 O(N)的算法：

int main()
{
    int n = 0;
    int count = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {count += i;// 计算 0~9 的和}
    return 0;
}

以下为空间复杂度为 O(N)的算法

int main()
{
    int n = 0;
    int count = 0;
    scanf("%d", &n);
    int* p = (int*)malloc(sizeof(int) * n);
    // 开拓大小为 n 的空间
    if (p == NULL)
    {perror("malloc fail");
        return -1;
          }
       free(p);
       p=NULL;
    return 0;
}

5.4 线性对数阶 O(NlogN)

无论是工夫复杂度还是空间复杂度，线性对数阶个别呈现在嵌套循环中，即一层的复杂度为 O(N)，另一层为 O(logN)

比如说循环应用二分查找打印：

int binary_search(int nums[], int size, int target) //nums 是数组，size 是数组的大小，target 是须要查找的值
{
    int left = 0;
    int right = size - 1;    // 定义了 target 在左闭右闭的区间内，[left, right]
    while (left <= right) {// 当 left == right 时，区间 [left, right] 依然无效
        int middle = left + ((right - left) / 2);// 等同于 (left + right) / 2，避免溢出
        if (nums[middle] > target) {right = middle - 1;    //target 在左区间，所以[left, middle - 1]
        }
        else if (nums[middle] < target) {left = middle + 1;    //target 在右区间，所以[middle + 1, right]
        }
        else {    // 既不在右边，也不在左边，那就是找到答案了
            printf("%d", nums[middle]);
        }
    }
    // 没有找到目标值
    return -1;
}
void func(int nums[], int size, int target)
{for (int i = 0; i < size; i++)
    {binary_search(nums, size, target);
    }
}

空间复杂度为 O(NlogN)的算法，最常见的莫非归并排序

void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){
    int i = startIndex, j=midIndex+1, k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1) {if(sourceArr[i] > sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
    }
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];
}
 
// 外部应用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex) {
    int midIndex;
    if(startIndex < endIndex) {midIndex = startIndex + (endIndex-startIndex) / 2;// 防止溢出 int
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}

5.5 平方阶 O(N^2^)

平方阶与线性对数阶类似，常见于嵌套循环中，每层循环的复杂度为 O(N)

工夫复杂度为 O(N^2^)，最常见的就是冒泡排序

void BubbleSort(int* a, int n)
{assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {if (a[i - 1] > a[i])
            {Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}

计算过程如下;

$$
T(N)=1+2+3+……+n-1=(n^2-n)/2=O(n^2)
$$

空间复杂度为 O(N^2^)，最简略的就是动静开拓。

{
    int n = 0;
    int count = 0;
    scanf("%d", &n);
    int* p = (int*)malloc(sizeof(int) * n*n);
    // 开拓大小为 n 的空间
    if (p == NULL)
    {perror("malloc fail");
        return -1;
          }
       free(p);
       p=NULL;
    return 0;
}

5.6 指数阶 O(2^N^)

指数阶的算法效率低，并不罕用。

常见的工夫复杂度为 O(2^N^)的算法就是递归实现斐波拉契数列：

int Fib1(int n)
{if (n == 1 || n == 2)
    {return 1;}
    else
    {return Fib1(n - 1) + Fib1(n - 2);
    }
}

粗略预计

$$
T(n)=2^0+2^1+2^2+…..+2^(n-1)=2^n-1=O(2^N)
$$

• 值得一提的是 斐波拉契的空间复杂度为 O(N)，因为在递归至最深处后往回归的过程中，后续空间都在销毁的空间上建设的，这样能大大提高空间的利用率。

空间复杂度为 O(2^N^)的算法个别与树无关，比方建设满二叉树

TreeNode* buildTree(int n) {if (n == 0)
        return NULL;
    TreeNode* root = newTreeNode(0);
    root->left = buildTree(n - 1);
    root->right = buildTree(n - 1);
    return root;
}

5.7 阶乘阶 O(N!)

阶乘阶的算法复杂度最高，简直不会采纳该类型的算法。

这是一个工夫复杂度为阶乘阶 O(N!)的算法

int func(int n)
{if (n == 0)
        return 1;
    int count = 0;
    for (int i = 0; i < n; i++) 
    {count += func(n - 1);
    }
    return count;
}

示意图：

• 空间复杂度为阶乘阶 O(N!)的算法并不常见，这里就不在一一列举。