数据结构----算法复杂度

1.数据结构前言

数据是杂乱无章的，我们要借助结构将数据管理起来

1.1 数据结构

数据结构(Data Structure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数

据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤，所以我们要学各式各样的数据结构，

如：线性表、树、图、哈希等

1.2 算法

算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤，⽤来将输⼊数据转化成输出结果。

好的算法能帮助我们更好的管理数据

数据结构是一种载体存储数据

算法是一种方法，管理数据

数据结构与算法不分家

学好数据结构可以提升面试和笔试

评估算法的好坏我们从复杂度进行评估

2.算法效率

/*给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。



示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]


提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105


进阶：

尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？*/
void rotate(int* nums, int numsSize, int k)
{
    while(k--)
    {
        int end=nums[numsSize-1];//创建一个临时变量将数组中最后一个数的值进行保存
        for(int i=numsSize-1;i>0;i--)//将数组中的数整体右移一位
        {
            nums[i]=nums[i-1];//在右移的时候我们要从后向前移，我们现将倒数第二个数赋值到最后一个数的位置上，然后随着i的变化进行右移操作
        }
        nums[0]=end;//最后我们将之前保存的值放到以一个位置上
    }


}

//但是这个存在限制，虽然这个代码没有问题，算法虽然没问题，但是超过时间限制，一但遇到大的数据，时间就变长了

第一种方法虽然算法是对的，但是一但遇到大的数据就计算不过来，计算时间很长

那么就衍生出了算法好坏的概念：算法复杂度

我们通过算法复杂度去衡量算法的好坏

复杂度分为时间复杂度和空间复杂度

算法在编写成可执⾏程序后，运⾏时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。在计算机发展的早期，计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发展，计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度

3.时间复杂度

时间复杂度铺垫

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率，

int main()
{
    //计算程序运行时间
    //计算时间我们要用到库time.h里的clock（）
    //可以记录在不同时间段的时间
    //我们记录开始和结束的时间，就得到了程序运行的时间
    int begin=clock();//定义起始时间
    int count = 0;
    for (int i = 0; i < 100000000; i++)
    {
        count++;
    }
    int end = clock();//定义结束时间

    //那么
    printf("time:%d", end - begin);//当前算法运行时间
    //得到的结果是0毫秒啊，如果我们给上一个亿的范围得到的就是59
    // 这个时间不是一个确切的时间
    //使用debug模式会加载一些调试信息，会占用一些我们程序的运行时间
    return 0;
}
//因为程序运行的时间不是一个确切的数，所以我们时间复杂度不能给出一个确切的数字

时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？

因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。
同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。
并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

因为程序运行的时间不是一个确切的数，所以我们时间复杂度不能给出一个确切的数字

我希望时间复杂度在编写算法之前就知道的，这个运行时间只能在程序编写好之后进行测试，不能在编写前计算评估

所以复杂度不是一个精确的数字，是一个粗估的数字

int main()
{


    int count = 0;//运行1次
    for (int i = 0; i < 100000000; i++)
    {
        count++;//运行了100000000次
    }
    int end = clock();


    return 0;
}
//那么运行次数是100000001次

程序效率：每条语句运行时间 * 次数

这个运行时间和编译环境和运行环境相关的，这个时间是不确定的，但是运行次数我们是能确定的

随着这个运行次数的增加，运行时间是正相关的，所以我们在计算时间复杂度的时候可以直接根据运行次数进行确定

// 请计算⼀下Func1中++count语句总共执⾏了多少次？

void Func1(int N)
{
    int count = 0;
    //这个for循环执行的次数就是N*N
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            ++count;
        }
    } 

    //这个for循环执行的次数就是2*N
    for (int k = 0; k < 2 * N; ++k)
    {
        ++count;
    } 
       int M = 10;
       //执行次数是10
    while (M--)
    {
        ++count;
    }
}


//那么我们判断的这个题的时间复杂度是T(N)=N^2+2N+10

//因为int count =0和int M=10的执行次数都是1，我们可以忽略不计的，对总的时间复杂度影响不大的

//T(N)=N^2+2N+10
//对于这个算术式，N^2的影响最大，2N+10对当前复杂度影响较小，是可以忽略不计的
// 
//那么我们就能得出T(N)=N^2

//可以得出时间复杂度是粗估，但是时间复杂度不是这么写的，我们要用上大O的渐进表示法
//O(n^2)就是这个题的时间复杂度了

O(n^2)就是这个题的时间复杂度了

实际中我们计算时间复杂度时，计算的也不是程序的精确的执⾏次数，精确执⾏次数计算起来还是很⿇烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执⾏次数意义也不⼤，因为我么计算时间复杂度只是想⽐较算法程序的增⻓量级，也就是当N不断变⼤时T(N)的差别，上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩，所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。

⼤O的渐进表⽰法

⼤O符号（Big O notation）：是⽤于描述函数渐进⾏为的数学符号

推导大O阶规则

1.时间复杂度函数式T(N)中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时，低阶项对结果影响越来越小，当N无穷大时，就可以忽略不计了。

2.如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大，这个系数2对结果影响越来越小，当N无穷大时，就可以忽略不计了。

3.T(N)中如果没有N相关的项目，只有常数项，用常数1取代所有加法常数。

时间复杂度示例

// 计算Func2的时间复杂度？
void Func2(int N)
{
    int count = 0;//次数是1，忽略不计
    //次数是2N
    for (int k = 0; k < 2 * N; ++k)
    {
        ++count;
    } 
      int M = 10;
      //次数是10
    while (M--)
    {
        ++count;
    } 
    printf("%d\n", count);
}
//那么这个题我们觉得的时间复杂度是O(2N)
//但是实际确实O(N),因为这里的倍数对我们的时间复杂度影响不是很大

那么这个题就对应上了规则2

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
    int count = 0;
    //执行了M次
    for (int k = 0; k < M; ++k)
    {
        ++count;
    } 
    //执行了N次
    for (int k = 0; k < N; ++k)

    {
        ++count;
    } 
    printf("%d\n", count);
}
//那么我们就得到了时间复杂度的函数式：T(N)=M+N
//M和N都是执行次数，都是变量，都会影响到时间复杂度的结果
//那么这个题的时间复杂度就是O(M+N)

//如果说M和N中有一个较大的项，那我们就保留高阶项
//如果M>>N的话，那么这里的时间复杂度就是O(M)
//如果M<<N的话，那么这里的时间复杂度就是O(N)
//如果M大约等于N的话，那么在时间复杂度里面就都保留

// 计算Func4的时间复杂度？
void Func4(int N)
{
    int count = 0;
    for (int k = 0; k < 100; ++k)
    {
        ++count;
    } 
    printf("%d\n", count);
}
//执行的次数是100，那么得出的函数式是T(N)=100
//那么我们的时间复杂度就是O(1)
//这里的1不是运行一次，而是代表所有的常数，可以说这个是一个表示法

//计算strchr的时间复杂度？  字符串的查找
const char* strchr(const char* str, int character)

{
    const char* p_begin = s;
    while (*p_begin != character)
    {

        if(*p_begin == '\0')
        return NULL;
        p_begin++;
    }
    return p_begin;
}
/*
T(N)取决于字符的长度N以及查找的位置
如果我们找了几次就找到了，那么这个时间复杂度就是O(1)
但是我们如果找到最后字符的时候才找到或者没有找到，那么我们这个时间复杂度就是O(N)
如果查找位置在中间的话，那么时间复杂度就是O(N/2)

所以这个题的时间复杂度取决于这个字符串的长度和查找的位置


但是对于这种有多个选项的时间复杂度呢，我们应该选择哪个作为时间复杂度呢？

O(1)是最好的情况
O(N)是最坏的情况
O(N/2)是平均的情况

*/

通过上⾯我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。

最坏情况：任意输⼊规模的最⼤运⾏次数(上界)

平均情况：任意输⼊规模的期望运⾏次数

最好情况：任意输⼊规模的最⼩运⾏次数(下界)

⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况

那么对于这个题来说，我们应该关注最差的情况，那么这个题的时间复杂度就是O(N)

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])//升序
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        } 
        if(exchange == 0)//说明数组是有序的，我们不用继续进行冒泡。直接跳出循环
            break;
    }
}
//当数组有序的情况下，外层循环执行一次，内层循环执行N次，因为数组有序，就只执行N次，那么时间复杂度就是O(N)
// 
//外层循环执行第一次的时候，内层循环执行N次，因为不是有序的，所以我们外层循要执行N次
/*
外1  2      3  ........n
内n-1   n-2            0
那么次数就是n-1+n-2+n-3+...+1
就是等差数列求和(n-1+1)*(n-1)/2
在这个结果中对结果影响最大的是N^2,所以这个代码的时间复杂度就是O(N^2)

*/

冒泡排序的时间复杂度为O(N^2)

void func5(int n)
{
    int cnt = 1;
    while (cnt < n)
    {
        cnt *= 2;
    }
}
/*
* 当N为10的时候，我们循环4次就停止了
* 假设执行的次数为x，那么2^x=n
* 那么x就等于log2 n   ,
* 
* 所以这里的时间复杂度是O(log2 n)
*/

注意课件中和书籍中 log2 n 、 log n 、 lg n 的表⽰

当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤。因此，⼀般情况下不管底数是多少都可以省略不写，即可以表⽰为 log n

不同书籍的表⽰⽅式不同，以上写法差别不⼤，我们建议使⽤ log n

对于计算机来说，这个底数的大小可以忽略不计的，因为影响很小

键盘是无法输入底数的

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
    if (0 == N)
        return 1;
    return Fac(N - 1) * N;
}
/*
递归的时间复杂度是多少呢
每次递归的时间复杂度是O(1)
总共有n个O(1),那么时间复杂度就是O(N)
*/

将每次递归的时间复杂度进行相加

4.空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象⼤⼩差异不会很⼤，所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。

注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定

空间复杂度计算⽰例

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        } 
        if(exchange == 0)
            break;
    }
}
/*
外面的for循环内局部变量end，内部还有变量exchange
内循环的变量i，总共三个变量
所以这里的空间复杂度是O(1)


*/

三个变量，那么这个空间复杂度就是O(3)

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
    if (N == 0)
        return 1;
    return Fac(N - 1) * N;
}
/*
F(N)->F(N-1)->....->F(1)->F(0)
总共的空间复杂度就是O(N)
*/

//通过动态申请内容也会涉及到空间复杂度的计算的

int func(int n)
{
    int arr[n] = malloc(sizeof(int) * n);
}
//这里的空间复杂度也是O(N)

5.常见复杂度对比

6.复杂度算法题--旋转数组

. - 力扣（LeetCode）

思路一:

首先将最后一位数进行保存，再将剩下的数字往右移一位，然后再将保存的数放到第一位

/*给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。



示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]


提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105


进阶：

尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？*/
void rotate(int* nums, int numsSize, int k)
{
    while(k--)
    {
        int end=nums[numsSize-1];//创建一个临时变量将数组中最后一个数的值进行保存
        for(int i=numsSize-1;i>0;i--)//将数组中的数整体右移一位
        {
            nums[i]=nums[i-1];//在右移的时候我们要从后向前移，我们现将倒数第二个数赋值到最后一个数的位置上，然后随着i的变化进行右移操作
        }
        nums[0]=end;//最后我们将之前保存的值放到以一个位置上
    }


}

//但是这个存在限制，虽然这个代码没有问题，算法虽然没问题，但是超过时间限制，一但遇到大的数据，时间就变长了

但是这个题有时间的限制，一但给到了一个很大的数字，那么就要消耗很多的时间，就不满足题目要求了将numsSize看作是N

这个代码的外层循环是k，内层循环是N-1,那么时间复杂度就是O(K*N),其实可以将K看做是N，都是变量，没啥区别，那么时间复杂度就是O(N^2)，这个时间复杂度效率很低，所以在提交的时候我们会遇到超出时间限制的错误

既然这里的时间复杂度是O(N^2),空间复杂度是O(1)

那我们能不能先办法将时间复杂度降到O(N)呢？

思路二：空间换时间

申请一个新数组，数组大小为numsSize

假设K=3, 我们将原数组的后三个数字要放到新数组的前面，然后旧数组剩下的数字我们直接搬到新数组内

申请新数组等大的空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中

最后我们还要将新数组的值挪到原数组中，为为原数组中的每个数进行重新赋值

void rotate(int* nums, int numsSize, int k)
{
    int newArr[numsSize];//创建一个数组大小和原先数组大小一样的数组
    for (int i = 0; i < numsSize; ++i)
    {
        newArr[(i + k) % numsSize] = nums[i];
    } 
    for (int i = 0; i < numsSize; ++i)
    {
        nums[i] = newArr[i];
    }
}
/*1 2 3 4 5 6 7
假设k是3，那么就是原数组后3数字放到新数组的前3个位置，原先的前4个数字放到新数组的后4个数字

newArr[(i + k) % numsSize] = nums[i];

第一次时，i=0 
newArr[(0 + 3) % 7] = nums[0];
newArr[(3) % 7] = nums[0];
newArr[3] = nums[0];
将原先数组的第一个赋值到新数组的第4个元素的位置

i=3时，就将原先数组的4放到新数组的最后一个位置

当i=4时，那么代码就是newArr[(4 + 3) % numsSize] = nums[4];
newArr[(7) %  7] = nums[4];
newArr[0] = nums[4];
将原先数组的下标为4的数字放到新数组的地址个位置


通过这个代码我们就实现了将原数组后k个数放到新数组的前k个位置，
将原数组的剩下的4个数据放到新数组的后4个位置


在后面的循环中，我们就将新数组中的值重新拿回到原数组内，因为我们打印的是原数组，在原数组中进行改变

*/

那么这个代码的时间复杂度是多少呢？

在第一个循环中，时间复杂度是O(N),在第二个循环中时间复杂度是O(N)

那么总的时间复杂度就是O(2N)，根据规则，消掉系数，那么最后的时间复杂度就是O(N)

这种方法的时间复杂度就达到了O(N)

但是这种思路的空间复杂度也是O(N)

我们申请了新的空间，这个空间大小是N个，那么空间复杂度就是O(N)

这个思路虽然时间复杂度降到了O(N)，但是我们是拿空间复杂度换的

思路三：

让时间复杂度为O(N),空间复杂度是O(1)

就是说明不需要额外申请空间

/*思路三
    1 2 3 4 5 6 7

n=7,当前数组内数据为7
旋转的k=3


第一步将前n-k个数据逆置  
这里的就是1 2 3 4
那么逆置后的结果就是4 3 2 1

第二步就是将后k个数据进行逆置
这里的就是5 6 7
逆置后的结果就是 7 6 5 

那么我们经历了一二步，得到了4 3 2 1 7 6 5

最后一步我们再将整体进行逆置
得到了5 6 7 1 2 3 4
*/
/*
我们在思路三已经想到了通过三步逆置达到效果
那我们就将逆置的函数写出来
我们在需要逆置的数组设置两个下标
最左边的下标是left
最右边的下标是right
那么我们每次将left和right的下标进行交换
交换完成之后我们将left和right进行++操作，逆置下一对数字
直到我们left和right重叠了我们就停止逆置操作

那么，理论成立，实践开始

*/


//逆置函数
void reverse(int nums, int left,int right)//逆置的数组   逆置开始的起始位置
{
    while (left < right)//这里写等于就是多此一举的
    {
        //left和right指向的数据进行交换
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;

        left++;
        right--;
    }
}


void rotate(int* nums, int numsSize, int k)
{
    k = k % numsSize;//不让k超过numsSize

    //前n-k个数据逆置
    reverse(nums, 0, numsSize - k - 1);

    //后k个数据逆置
    reverse(nums, numsSize-k, numsSize-1);

    //整体逆置
    reverse(nums, 0, numsSize - 1);
}

/*
如果当前数组里面只有-1，但是我们要进行逆置2次，该怎么实现


我们需要对k进行处理，让k余上数组的大小，可以避免多余的逆置操作
一但逆置的次数大于数组的长度，这个步骤就起到了作用，减小了代码的运行时间

    k = k % numsSize;//不让k超过numsSize

*/

第一步将前n-k个数据逆置

第二步就是将后k个数据进行逆置

最后一步我们再将整体进行逆置

我们还要对逆置的次数进行取余，保证次数要小于数组的长度

我们对这个代码进行时间复杂度的分析

reverse函数只有一个变量tmp，那么空间复杂度就是O(1)

对于逆置函数来说，我们调用了三次

第一次调用要交换的次数是(numsSize - k) / 2

第二次交换的次数是k / 2

第三次交换的次数是numsSize / 2

那么总的交换次数就是(numsSize - k) / 2 + k / 2 + numsSize / 2。

所以时间复杂度就是O(N)