自学内容网 自学内容网

数据结构第一讲:复杂度

博客简介:
1.该博客是数据结构第一讲,是数据结构初阶的内容,后续会继续输出数据结构高阶的内容
2.数据结构初阶内容全部由C语言来编写

1.数据结构前言

1.1什么是数据结构

将数据比作成一群在草原上的绵羊,绵羊是无序的,如果我们要查找一只叫做“贝蒂”的绵羊,一只一只查找是很耗时耗力的,所以我们要将所有的绵羊组织起来,对他们进行管理,以便于后边的增删查改等操作

像这样的将数据组织、存储的方式就叫做数据结构

1.2算法

算法其实就是解决问题的方法

2.算法效率

首先我们先看一道例题,然后在研究算法效率

案例:轮转数组链接: 力扣链接
我们直接将所写的代码拿上来:

void rotate(int* nums, int numsSize, int k) {
    //思路:每一次循环就将一个数字进行轮转
    while(k--)
    {
        int begin = *(nums+numsSize-1);
        for(int i = numsSize-1; i>0; i--)
        {
            *(nums+i) = *(nums+i-1);
        }
        *nums = begin;
    }
}

当我们提交时,我们可以发现:出错了!原因为:
在这里插入图片描述
那么为什么会出现超出时间限制这个错误呢,我们往下看:

2.1复杂度的概念

算法的运行需要时间,也需要空间,衡量一个算法的好坏通常是从时间和空间两个方面来看,也就是时间复杂度和空间复杂度

3.时间复杂度

时间复杂度判断总结:

1.只保留高阶项,保留高阶项后要省略掉低阶项
2.高阶项前的系数可以忽略
3.所有的常数项都要被替换成1
4.对于以log形式的函数都可以将底数忽略,写成是logN或者lgN
5.按照最坏的哪一种情况的复杂度作为算法的时间复杂度

下面我们来看具体的分析案例来加深对时间复杂度的理解:

3.1案例1

// 计算Func2的时间复杂度?
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
// 计算Func2的时间复杂度?
void Func2(int N)
{
    int count = 0;
    for (int k = 0; k < 2 * N; ++k)
    {
        //for循环,时间复杂度为2*N
        ++count;
    }
    int M = 10;
    while (M--)
    {
        //时间复杂度为M,M为10,那么时间复杂度就是10
        ++count;
    }
    printf("%d\n", count);
}
//所以说:该算法的时间复杂度为2*N+10
//表示方法为:O(N)【保留了高阶项2*N,将高阶项前的系数可以忽略】

3.2案例2

// 计算Func3的时间复杂度?
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);
}
// 计算Func3的时间复杂度?
void Func3(int N, int M)
{
    int count = 0;
    for (int k = 0; k < M; ++k)
    {
        //时间复杂度为M
        ++count;
    }
    for (int k = 0; k < N; ++k)
    {
        //时间复杂度为N
        ++count;
    }
    printf("%d\n", count);
}
//所以它的时间复杂度就是M+N
//表示为O(N)即可

3.3案例3

// 计算Func4的时间复杂度?
void Func4(int N)
{
    int count = 0;
    for (int k = 0; k < 100; ++k)
    {
        ++count;
    }
    printf("%d\n", count);
}
// 计算Func4的时间复杂度?
void Func4(int N)
{
    int count = 0;
    for (int k = 0; k < 100; ++k)
    {
        //时间复杂度为100
        ++count;
    }
    printf("%d\n", count);
}
//它的时间复杂度为100
//表示为O(1)

3.4案例4

// 计算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;
}
// 计算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;
}
//我们假设字符串中一共有N个字符
//第一种情况(最好的情况):
//查找的第一次就查找到了目标字符,那么这时的时间复杂度就是O(1)
//第二种情况(中间情况):
//目标字符组在字符串的中间位置,那么这时的时间复杂度就是N/2,表示为O(N)
//第三种情况(最坏的情况):
//当目标字符在我们要查找的字符串末尾时,这时的时间复杂度为O(N)
//
//取最坏的情况作为算法最终的时间复杂度,也就是O(N)

3.5案例5

// 计算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;
    }
}
// 计算BubbleSort的时间复杂度?
//冒泡排序函数
void BubbleSort(int* a, int n)
{
    //这个函数将循环嵌套使用
    for (size_t end = n; end > 0; --end)
    {
        //外层循环的次数为N
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            //外层每循环一次,内层都要交换N-1次
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}
//所以说该算法的时间复杂度为一个等差数列进行求和的结果:
//N N-1 ...... 2 1
//结果为N(N+1)/2 , 表示为O(N^2)

3.6案例6

void func5(int n)
{
    int cnt = 1;
    while (cnt < n)
    {
        cnt *= 2;
    }
}
void func5(int n)
{
    int cnt = 1;
    while (cnt < n)
    {
        cnt *= 2;
    }
}
//当N取10时,我们来看这个算法是怎么运行的:
//cut 1 2 4 8  16
//ret 2 4 8 16 32
//由于cnt并不是从0开始,一直顺序增加到10的,而是不停的*2做到的,所以此时的时间复杂度并不是O(n)
//当N为10时,循环了4次就做到了,通过我们的分析可以看出,该算法的时间复杂度为O(logN)

3.7案例7

// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{
    if (0 == N)
        return 1;
    return Fac(N - 1) * N;
}
// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{
    if (0 == N)
        return 1;
    return Fac(N - 1) * N;
}
//这里是计算递归函数的时间复杂度
//不难看出,该函数是从Fac(N-1)递归到了Fac(0)
//也就是从0到N递增运行,时间复杂度为O(N)

我们已经了解到了时间复杂度的计算方法,那么分析一个算法的好坏是否已经是了然于胸了呢,其实不是,判断一个算法的好坏还需要判断它的空间复杂度
当前来说,内存空间是相对而言十分廉价的,我们经常会使用空间来换取时间,那是不是就说明空间可以随意地使用呢,肯定不对!所以我们仍然需要了解空间复杂度的计算方法:

4.空间复杂度

空间复杂度计算针对的仅仅是算法进行过程中临时开辟的内存

4.1案例1

// 计算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;
    }
}
// 计算BubbleSort的时间复杂度?
void BubbleSort(int* a, int n)
{
    for (size_t end = n; end > 0; --end)
    {
        //size_t end = n  时间复杂度为1
        int exchange = 0;
        //int exchange = 0  时间复杂度为2(1+1=2)
        for (size_t i = 1; i < end; ++i)
        {
            //size_t i = 1  时间复杂度为3
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}
//程序运行时只对三个变量进行了初始化,所以时间复杂度为O(1)

4.2案例2

// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{
    if (N == 0)
        return 1;
    return Fac(N - 1) * N;
}
// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{
    if (N == 0)
        return 1;
    return Fac(N - 1) * N;
}
//每一次函数递归时都要创建一次函数
//所以它的时间复杂度为O(N)

5.常见复杂度对比

在这里插入图片描述
在这里插入图片描述

6.轮转数组题目分析

我们有了上述的知识之后,再来看我们一开始写的题目:

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];
        }
        nums[0] = end;
    }
}

对它进行时间复杂度的分析:

void rotate(int* nums, int numsSize, int k) {
    while (k--)
    {
        //外层循环k次
        int end = nums[numsSize - 1];
        for (int i = numsSize - 1; i > 0; i--)
        {
            //外层每循环一次,内层进行N-1次操作
            nums[i] = nums[i - 1];
        }
        nums[0] = end;
    }
}
//时间复杂度为O(N^2)
//是一个等差数列

通过复杂度对比表格可以看出,O(n^2)复杂度需要的时间很长,那么我们是否可以将这个算法换成是O(N)或者是O(1)这些算法呢?优化如下:

6.1优化1

思路分析:
申请新数组空间,先将后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];
    }
}

时间复杂度分析:

void rotate(int* nums, int numsSize, int k)
{
    int newArr[numsSize];
    for (int i = 0; i < numsSize; ++i)
    {
        //时间复杂度为numsSize
        newArr[(i + k) % numsSize] = nums[i];
    }
    for (int i = 0; i < numsSize; ++i)
    {
        //时间复杂度为numsSize
        nums[i] = newArr[i];
    }
}
//所以说该算法的时间复杂度为O(N)
//但是它的空间复杂度为O(N),因为创建了一个新的数组,这个数组的大小为numsSize
//这里就是一个空间换取时间的案例

6.2优化2

思路分析:
在这里插入图片描述

void reverse(int* nums, int begin, int end)
{
while (begin < end) {
int tmp = nums[begin];
nums[begin] = nums[end];
nums[end] = tmp;
begin++;
end--;
}
}
void rotate(int* nums, int numsSize, int k)
{
k = k % numsSize;
reverse(nums, 0, numsSize - k - 1);
reverse(nums, numsSize - k, numsSize - 1);
reverse(nums, 0, numsSize - 1);
}

时间复杂度分析:

void reverse(int* nums, int begin, int end)
{
while (begin < end) {
int tmp = nums[begin];
nums[begin] = nums[end];
nums[end] = tmp;
begin++; 
end--;
}
}
void rotate(int* nums, int numsSize, int k)
{
k = k % numsSize;
reverse(nums, 0, numsSize - k - 1);
//时间复杂度为O(N)
reverse(nums, numsSize - k, numsSize - 1);
//时间复杂度为O(N)
reverse(nums, 0, numsSize - 1);
//时间复杂度为O(N)
}
//所以该函数的时间复杂度为O(N)
//但是它的空间复杂度只有O(1)

原文地址:https://blog.csdn.net/2301_79761834/article/details/140582791

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!