时间复杂度与空间复杂度（一）

绪论

       本章是数据结构的开始，我们在判断一个算法一般是用时间复杂度和空间复杂度来衡量好坏的评判工具。

话不多说安全带系好，发车啦（建议电脑观看）。

思维导图：

要XMind思维导图的话可以私信哈

1.时间复杂度        

知识点：

时间复杂度：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一 个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知 道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例。（简单来说时间复杂度的计算，并不是计算其花费的时间，而是计算其运行时的执行次数）

细节（注意点）：

如何来算一个算法的时间复杂度：

我们在算时间复杂度的时候一般会用到 大O渐进表示法：

对于常数次的时间复杂度来说直接用1来表示即：O(1)

在算时间复杂度时我们只取大概的量级（取到最大的量级）

对于一个N * 常数时 我们可以直接省略所乘的常数次 ： O（N）（对于一个N来说乘上一个常数对数据影响并不大）

在算时间复杂度是我们一般都是直接算他的最坏情况 (因为有些时间复杂度无法直接算出，可能分最好和最坏的情况)

把log以2为底的N的对数 一般写成直接logN

练习：

例1：

void Func2(int N)
{
     int count = 0;
     for (int k = 0; k < 2 * N ; ++ k) // 2 * N == N
     {
         ++count;
     }
     int M = 10;
     while (M--)// O(1)
     {
         ++count;
     }
     printf("%d\n", count);
}

上面的Fun2时间复杂度: O(N)  (  一般以： ...... 的时间复杂度是： O（...） )

例2：

void Func2(int N)
{
     int count = 0;
     for (int k = 0; k < 2 * N ; ++ k) // 2 * N == N
     {
         ++count;
     }
     int M = 10;
     while (M--)// O(1)
     {
         ++count;
     }
     printf("%d\n", count);
}

例3：

void Func3(int N, int M)
{
 int count = 0;
 for (int k = 0; k < M; ++ k)
 {
 ++count;
 }
 for (int k = 0; k < N ; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}
//

因为不知道 M N 的关系 所以写成 O(M+N)

如果 M >> N  : O(M)

反之 ：O (N)

如果 M == N : O(N) / O (M)