算法小结 | Dev

算法与数据结构的关系

数据结构研究的内容：是如何按一定的逻辑结构，将数据组织起来，并选择合适的存储结构表示方法，把逻辑结构组织好的数据存储到计算机的存储器中。

算法研究的目的：为了更有效的处理数据，提高数据运算效率。

数据的运算是定义在数据的逻辑结构上，运算的实现要在存储结构上进行。

定义

算法就是描述解决问题的方法

特性

输入项：一个算法有0个或多个输入，0个输入是指算法本身有初始条件；
输出项：一个算法有1个或多个输出，没有结果输出的算法是毫无意义的；
有穷性：算法必须能在执行有限个步骤后终止；
确定性：算法的每一步必须有确切的定义；
可行性：算法中的每个计算步骤都可以在有限时间内完成；

设计要求

正确性：评价一个算法优劣的最重要的标准；
可读性：一个算法可供人们阅读的容易程度；
健壮性：一个算法对不合理数据输入的反应能力和处理能力，也称为容错性；
时间效率高：执行时间少，时间复杂度小；
存储量低：存储空间少，空间复杂度小；

效率衡量方法

同一个问题可用不同的算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。

一个算法的评价主要从时间复杂度和空间复杂度来考虑。

时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。

T(n)=Ο(f(n))

因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

推导大0阶方法

用常数1取代运行时间中所有加法常数;
在修改后的运行次数函数中,只保留最高阶项;
如果在最高阶项存在且不是1,则去除与这个项相乘的常数;

常见的时间复杂度

常数阶： O(1)

int sum = 0;                // 执行 1 次
sum += (n + 1) * n / 2;     // 执行 1 次
printf("sum: %d \n", sum);  // 执行 1 次
  
// 1 + 1 + 1 = 3
// 时间复杂度为：O(1)

线性阶：O(n)

int i = 0;                // 执行 1 次
while(i < n) {            // 执行 n 次
  printf("i: %d \n", i);  // 执行 n 次
  i++;                    // 执行 n 次
}
// 1 + n + n + n = 3n + 1
// 时间复杂度：O(n)

对数阶：O($log{n}$)

let sum = 1;        // 执行 1 次
while (sum < n) {   // 执行 logn 次
  sum *= n;         // 执行 logn 次
}
// 1 + logn + logn = 2logn + 1
// 时间复杂度：O(logn)

幂数阶：O($n^2$)

for (int i = 0; i < n; i++) {     // 执行 n 次
  for (int j = 0; j < n; j++) {   // 执行 n * n 次
    printf("i am here !\n");      // 执行 n * n 次
  }
}
// n + n^2 + n^2 = 2n^2 + n
// 时间复杂度：O(n^2)

线性对数阶：O(${n}log{n}$)
指数阶：O($2^n$)
阶乘阶：O($n!$)

O(1) < O($log{n}$) < O(n) < O(${n}log{n}$) < O($n^2$) < O($2^n$) < O($n!$)

最坏情况与平均情况

最坏的情况运行时间是一种保证, 那就是运行时间将不会比这更坏。

平均运行时间是所有情况中最有意义的,因为它是期望的运行时间。

对于算法的分析，一种方法就是计算所有情况的平均值，这种时间复杂度的计算的方法称为平均时间复杂度。另一种方法是计算最坏的情况下时间复杂度，这种方法称为最坏时间复杂度。

一般没有特殊情况下，都是指最坏时间复杂度。

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令，常数，变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关。

这样只需要分析该算法在实现时所需要的辅助空间就可以了。

//  问题: 数组逆序,将一维数组a中的n个数逆序存放在原数组中.

// 实现一 ：
    int temp;
    for(int i = 0; i < n/2 ; i++) {
        temp = a[i];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }

    for(int i = 0;i < 10;i++) {
        printf("%d\n",a[i]);
    }

// 实现二： 
    int b[10] = {0};
    for(int i = 0; i < n;i++) {
        b[i] = a[n-i-1];
    }
    for(int i = 0; i < n; i++) {
        a[i] = b[i];
    }
    for(int i = 0;i < 10;i++) {
        printf("%d\n",a[i]);
    }

算法一：借助临时变量temp，与问题规模n大小无关，所以空间复杂度为 O(1)
算法二：借助一个大小为n的辅助数组b，所以空间复杂度为 O(n)

对一个算法，其时间复杂度和空间复杂度往往会互相影响。当追求一个较好的时间复杂度时，可能会导致占用较多的存储空间。即可能会使用空间复杂度的性能变差。反之亦然。

不过，通常情况下，鉴于运算空间较为充足，人们都以算法时间复杂度作为算法优先的衡量指标。