时间复杂度和空间复杂度_时间复杂度 阶乘

一、数据结构的基本概念
数据：描述客观事实的符号，是计算机中可以操作的对象，能被计算机识别，并输给计算机处理的符号集合。
数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被成为记录。、
数据对象：是性质相同数据元素的集合，是数据的一个子集
数据项：一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单位。
数据结构：相互之间存在一种或者多种特定关系的数据元素的集合。可分为逻辑结构和物理结构。

二、算法
算法：解决特定问题的步骤的描述
特性：
—输入：有零个输入或者多个输
—输出：只有一个或者多个输出
—有穷型性：算法在执行有限个步骤时，会自动结束而不会陷入无限循环里面
—确定性：算法的每一步都有确定的含义而不会出现二义性
—可行性：算法的每一步都可以通过有限次数完成。

要求：
正确性、可读性、健壮性、时间效率高而且空间使用率低、简单性。
算法的复杂度分为时间复杂度和空间复杂度。
时间复杂度：时间复杂度实际上是一个函数，代表基本操作重复执行的次数，进而分析函数虽变量的变化来确定数量级，数量级用O表示，所以算法的时间复杂度为：
T（n）=O（f（n））；
在一个算法存在最好、平均、最坏三种情况，我们一般关注的是最坏情况，原因是，最坏情况是任何输入实例在运行时间的上界，对于某些算法来说，最坏情况出现的比较频繁，从大体上来看，平均情况和最坏情况一样差。
一般O（n）的计算方法：
—用1代替所有运行时间中出现的加法常数；
—在修改后的运行函数中保留最高阶的项；
—如果最高阶的项系数不是1，则去除这个项系数。
递归算法的时间复杂度为：递归总次数*每次递归中基本操作执行的次数。
常见的时间复杂度有以下七种：O（1）常数型；O（log2N）对数型，O（N）线性型，O（Nlog2N）二维型，O（N^2)平方型，O（N^3)立方型，O（2^N）指数型。

空间复杂度：
是对一个算法在运行过程中临时占用存储空间的度量，一个算法在计算机存储器上所占用的存储空间包括存储算法本身所占用的空间，算数和输入输出所占用的存储空间以及临时占用存储空间三个部分，算法的输入输出数据所占用的存储空间是由待解决的问题来决定的，通过参数表由调用函数而来，它随本算法的不同而改变，存储算法本身所占用的存储空间有算法的书写长短成正比。算法在运行过程中占用的临时空间由不同的算法决定。

int x = 90;
     int y = 100;
     while (y > 0)
     {
          if (x > 100)
          {
              x = x - 10;
              y--;
          }
          else
          {
              x++;
          }
     }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：O(1)，空间复杂度：O(1);

2、当有若干个循环时，时间复杂度是和嵌套层数最多的循环语句中最内层的频度决定的

for (i = 0; i < n; i++)
     {
          for (j = 0; j < i; j++)
          {
              for (k = 0; k < j; k++)
              {
                   x++;
              }
          }
     }
1
2
3
4
5
6
7
8
9
10

时间复杂度：O(n^3),空间复杂度：O（1）
3、求二分法的时间复杂度

int select(int a[], int k, int len)
{
     int left = 0;
     int right = len - 1;
     while (left <= right)
     {
          int mid = left + ((right - left) >> 2);
          if (a[mid] == k)
          {
              return 1;
          }
          else if (a[mid] > k)
          {
              right = mid - 1;
          }
          else
          {
              left = mid + 1;
          }
     }
     return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

分析：

在最坏的情况下循环x次后找到，n/（2^x）=1;x=log2n;
所以二分查找的时间复杂度为：O（log2n）；空间复杂度O（1）；
4、用递归算法求n的阶乘

int fac(int n)
{
     if (n <= 2)
     {
          return n;
     }
     else
     {
          return fac(n - 1)*n;
     }
}
1
2
3
4
5
6
7
8
9
10
11

n的阶乘的时间复杂度很简单：就是n次递归算法，所以为O（n），空间复杂度O（n），递归的深度是n。
5、斐波那契数列

int fib(int n)
{
     if (n < 2)
     {
          return 1;
     }
     else
     {
          return fib(n-1) + fib(n - 2);
     }
}
1
2
3
4
5
6
7
8
9
10
11

分析：

将其用流程图画出来发现是一个完全二叉树，节点数为2^n-1,深度为n，根据最坏情况，时间复杂度为O（2^n），空间复杂度为O（n）；