算法在计算中的作用

前言

算法在基因工程，互联网，电子商务和制造业中都有广泛的应用。最近的智能驾驶和人工智能也处处有着算法的影子。

数据结构

数据结构是数据元素存在的一种形式，有线性和非线性的区别。常见的线性的有链表，数组，栈和队列，非线性的有树，图等等。每一种数据结构在特定情况下有它的优势，也有这不一样的局限性。

数组：在内存中的物理存储需要连续性，不便于增加元素和删除元素。但是访问的时间复杂度却是很高效。

链表：在内存中的存储位置可以是离散的，虽然在访问元素方面不如数组，但是增加和删除元素的时候极为方便，尤其是问题规模越大的时候。

散列表：也成哈希表，个人理解是数组和链表的一种结合体。数据元素的数据通过哈希函数与数组元素的下标一一对应，这样有助于提高查询访问的效率。同时这些数组并不存储数据，只是存储数据的关键字，它们通过链表来存储数据元素，每一个数组元素是一个数据链表的表头结点，这样也便于增删操作。下图为数组，链表的时间复杂度。

问题规模为n	查询时间复杂度	增删时间复杂度	存储密度
数组	O(1)	O(n)	100%
链表	O(n)	O(1)	50%

技术

算法也可以看作是一门技术，可以帮助工程师通过分析，推理证明设计合理的方法，来解决问题。如最小生成树问题，统计中的中位数问题，旅行商问题等等都需要算法这门技术来解决。

难题

算法可能有多个解，因此有最优解的概念。同时有些问题无法很好的解决，这些问题成为NP问题，在没有准确的解的情况下，就衍生除了近似解的方法了。

算法比较

插入排序：

数据结构：单链表

代码：

void insert_sort(linklist list, elemtype data[10]) {
 
    lnode *p = list;
    
    for(int i = 0; i < 10; i++) {
        while (p->next)
        {
            lnode *q = p->next;
            if(q->data > data[i]) {
                lnode *node = (lnode *) malloc(sizeof(lnode));
                node->data = data[i];
                node->next = q;
                p->next = node;
                break;
            }
            p = p->next;
        }
        if(!p->next) {
        lnode *node = (lnode *) malloc(sizeof(lnode));
        node->data = data[i];
        node->next = NULL;
        p->next = node;
        }
        p = list;
    }
}

输出结果：

归并排序：

数据结构: 数组

代码：

void merge(int a1[MAXSIZE], int b1[MAXSIZE], int low, int mid, int high) {
    int i = low, j = mid+1, k = low;
    while (i <= mid && j<= high)
    {
        if(a1[i] < a1[j]) {
            b1[k++] = a1[i++];
        }else {b1[k++] = a1[j++];
        }
    } 
    while(i <= mid) b1[k++] = a1[i++];
    while(j <= high) b1[k++] = a1[j++];
}

void merge_sort(int a[MAXSIZE], int b[MAXSIZE], int low, int high) {

    if(low == high) {
        b[low] = a[low];
        return;
    }
    int mid = (low + high) / 2;
    int temp[MAXSIZE] = {0};
    merge_sort(a, temp, low, mid);
    merge_sort(a, temp, mid + 1, high);
    merge(temp, b, low, mid, high);
}

输出结果：