《数据结构》时间复杂度

                                                  

目录

 一、算法效率

二、时间复杂度

   为何要使用大O渐进法 

   最坏情况、平均情况、最好情况

   时间复杂度实战

三、空间复杂度

---

 一、算法效率

       有两种算法效率：时间效率(Time Efficiency)和空间效率(Space Effiency)。时间效率也称为时间复杂度(Time Complexity)，指出算法运行有多快；空间效率有称为空间复杂度(Space Complexity)，指出算法需要多少额外的空间。

二、时间复杂度

我们先来看下面一段代码，结合代码理解起来更加轻松

    void func1(int N) {
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                count++;
            }
        }
        for (int k = 0; k < 2 * N; k++) {
            count++;
        }
        int M = 10;
        while ((M--) > 0) {
            count++;
        }
        System.out.println(count);
 
    }

首先我们观察代码可以得到F(N)=N^2+2*N+10

1.假设我们认为N=10；那么我们这个代码的运次数为N = 10 F(N) = 130

2.假设我们认为N=100；那么我们这个代码的运行次数为N = 100 F(N) = 10210

        我们可以观察到，当N的值变大，而所谓我们加的常数已经变得非常小了

3.假设我们为人N=100；那么我们这个代码的运行次数为N = 1000 F(N) = 1002010

        我们可以观察到，当N的值变大，而所谓我们2*N也会变得微不足道

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，这里我们使用的是大O的渐进表示法；
推导大O阶方法： 
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶

所以，综上所述计算出此代码的时间复杂度为O(N)；

那么为什么我们要用1来表示所以的常数呢，这是因为计算机的运行速度是非常快的，每秒可能就可以执行上亿此的运算，那么常数次的执行次数与我们计算机的运算速度相比，可能与执行一次的运行速度相差不会太大，所以我们就使用1来代替所有的常数项，那么只有循环次数为常数的算法的时间复杂度相应的就是O(1)。

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

为何要使用大O渐进法

        很多铁铁都会有这样的问题；首先我们了解到计算机中是有分类的，如果要评判代码的好坏首先会想到考虑代码运行的效率；而代码运行的效率首先挂钩的是计算机的CPU的计算速度，也跟电脑的GPU挂钩，而每台电脑都是有着稍微差异的，不可能将一台最新款的电脑运行的代码跟几十年前的电脑代码速度来比较，那么就发明出了大O渐进法来衡量代码的好坏；

        那我们为什么只保留对结果影响最大的那一项呢？我们知道时间复杂度描述的对象是一个算法，而不是某一次的运算，那么当我们使用这个算法并向里面传入一个能够影响算法基本操作执行次数的变量时，我们并不能确定我们输入的N的值是多少，N就有可能是任何值，当N比较小时，也许别的项与最高阶项的结果差距并没有那么大，但是当N的值越来越大时，最高阶项的值与其他项的值的差距也就越来越大了，我们还是以上面的代码为例，当我们的N在不断的变大时，因为其余项对结果的影响相对来说比较小，那么我们就可以忽略他们对结果的影响，只保留对结果影响最大的那一项来表示我们的时间复杂度；

最坏情况、平均情况、最好情况

        有些算法是存在最坏情况、平均情况、最好情况的

最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到

最坏情况就是代表这个代码的算法在最差的情况下需要多少次来找到数据

平均情况就是折中

最好情况就是大部分人都想的， 一次就可以找到要寻找的数据

而我们平时讨论的时间复杂度都为最坏情况，所以时间复杂度为O(N)；

时间复杂度实战

        我们来做几道题练习一下时间复杂度

void func2(int N) {//1
int count = 0;//2
for (int k = 0; k < 2 * N ; k++) {//3
count++;//4
}//5
int M = 10;//6
while ((M--) > 0) {//7
count++;//8
}//9
System.out.println(count);//10
}//11

首先我们可以观察到 第3行中循环次数为2*N，第7行中循环次数为M=10；

所以我们可以得到

O(N)=O(2*N+10)=O(2*N+1)=O(N）所以我们得到此代码的时间复杂度为O(N)

void func3(int N, int M) {//1
int count = 0;//2
for (int k = 0; k < M; k++) {//3
count++;//4
}//5
for (int k = 0; k < N ; k++) {//5
count++;//6
}//7
System.out.println(count);//8
}//9

我们可以观察到3、5行的循环次数为O(M+N),因为我们的N和M是两个未知数

所以我们得到此代码的时间复杂度为O(M+N)

void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++;
}
System.out.println(count);
}

我们可以观察到此代码总循环次数为100次，O(100)=O(1);

所以我们得到此代码的时间复杂度为O（1）

void bubbleSort(int[] array) {//1
    for (int end = array.length; end > 0; end--) {//2
        boolean sorted = true;//3
    for (int i = 1; i < end; i++) {//4
        if (array[i - 1] > array[i]) {//5
            Swap(array, i - 1, i);//6
                sorted = false;//7
        }//8
    }//9
        if (sorted == true) {//10
            break;//11
        }//12
    }//13
}//14

我们观察可以发现这是一个改进过的冒泡排序算法，而对于这种我们是要有判断最坏情况、平均情况、最好情况的评判， 我们可以考虑到，经过一次排序后可能会变得已经有序，也有可能需要全部重新排一次才会有序

最坏情况:O(N^2)

平均情况:O(N^2/2)

最好情况:O(1)

而我们之前提到过，对于这些我们讨论到的是最坏情况，所以时间复杂度为O(N^2)

为大家附上一张图，这张图是大部分排序的时间复杂度

我们可以看到对排序法的颜色有区别 在紫色标注的为简单排序，其余的为高级排序

 

int binarySearch(int[] array, int value) {
int begin = 0;
int end = array.length - 1;
while (begin <= end) {
int mid = begin + ((end-begin) / 2);
if (array[mid] < value)
begin = mid + 1;
else if (array[mid] > value)
end = mid - 1;
else
return mid;
}
return -1;
}

这是一个二分查找算法

第一次查找： T(1) = n/2

第二次查找： T(2) = n/2^2

第三次查找： T(3) = n/2^3

…

第M次查找： T(M) = n/2^M

数据规模大于等于1即 n/2^M >=1 ，说明不能再继续二分查找的操作，当数据规模达到最小值1时即n/2^M =1则是最坏的查找情况。

T(M) = n/2^M = 1 得到O(N)=log2n，二分查找的时间复杂度为以2为底数n为指数的对数
（之后会出一篇专门分析二分查找算法的时间复杂度文章）

long factorial(int N) {
    return N < 2 ? N : factorial(N-1) * N;
}

这是一个递归，其实在编程语言刚开始发展的时候，是没有循环的，那么循环是怎么来实现的？就是它，递归；c刚刚问世的时候，都是使用递归才实现循环的

那么我们就可以将它看做是一个循环，而循环次数就是它的递归次数

我们可以得到递归次数为N，所以时间复杂度为O(N)

int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

这是一个计算斐波那契数列第N项的递归

我们将剩余位置补齐

 我们来计算一下

递归第六项我们需要计算32项

递归第五项我们需要计算16项

递归第四项我们需要计算8项

递归第三项我们需要计算4项

结合规律，我们可以发现每次计算的次数是2^N

所以我们可以得到，时间复杂度为O(2^N)

三、空间复杂度

空间复杂度的概念：

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度

空间复杂度也使用大O渐进法来表示

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度

那么空间复杂度是如何来计算的呢？

我们继续来结合代码学习

void bubbleSort(int[] array) {
    for (int end = array.length; end > 0; end--) {
        boolean sorted = true;
    for (int i = 1; i < end; i++) {
        if (array[i - 1] > array[i]) {
            Swap(array, i - 1, i);
                sorted = false;
        }
    }
        if (sorted == true) {
                break;
        }
    }
}

 我们已经知道，空间复杂度是计算运行过程中开辟的临时空间

代码在运行中开辟了常数个额外空间，所以空间复杂度为 O(1)

int[] fibonacci(int n) {
    long[] fibArray = new long[n + 1];
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n ; i++) {
        fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    }
    return fibArray;
}

此代码在循环运行中开辟了N个临时空间，所以空间复杂度为O(N)

long factorial(int N) {
     return N < 2 ? N : factorial(N-1)*N;
}

在此代码中递归开辟了N块临时空间，可以结合图来理解一下

 每一次递需要保存每一次递后的值，所以需要一块临时的空间，以便于保存归时候的值