C语言算法复杂度

简介: 【10月更文挑战第20天】

【10月更文挑战第20天】
数据是杂乱无章的,我们要借助结构将数据管理起来

1.1 数据结构

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

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

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

1.2 算法

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

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

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

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

数据结构与算法不分家

image.png

image.png

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

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

/*给定一个整数数组 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;//最后我们将之前保存的值放到以一个位置上
    }


}

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

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

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

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

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

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

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

时间复杂度铺垫

定义:在计算机科学中,算法的时间复杂度是⼀个函数式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;
}
//因为程序运行的时间不是一个确切的数,所以我们时间复杂度不能给出一个确切的数字

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

  1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系,⽐如同⼀个算法程序,⽤⼀个⽼编译器进⾏编译和新编译器编译,在同样机器下运⾏时间不同。

  2. 同⼀个算法程序,⽤⼀个⽼低配置机器和新⾼配置机器,运⾏时间也不同。

  3. 并且时间只能程序写好后测试,不能写程序前通过理论思想计算评估。

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

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

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

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月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
106 1
|
2月前
|
存储 算法 C语言
【C语言】二分查找算法
【C语言】二分查找算法
|
2月前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
|
4月前
|
机器学习/深度学习 存储 并行计算
C语言与机器学习:K-近邻算法实现
C语言与机器学习:K-近邻算法实现
64 0
|
6月前
|
算法 C语言
C语言----判断n是否是2的次方数,利用到按位与&,算法n&(n-1)
C语言----判断n是否是2的次方数,利用到按位与&,算法n&(n-1)
|
7月前
|
存储 搜索推荐 算法
C语言数据结构算法,常用10种排序实战
插入排序(Insertion Sort) 希尔排序(Shell Sort) 选择排序(Selection Sort) 冒泡排序(Bubble Sort) 归并排序(Merge Sort) 快速排序(Quick Sort) 堆排序(Heap Sort) 基数排序(Radix Sort)
70 1
C语言数据结构算法,常用10种排序实战
|
6月前
|
算法 Java C语言
Java中的算法与C语言中的函数
Java中的算法与C语言中的函数
46 2
|
7月前
|
算法 搜索推荐 C语言
C语言中的经典算法实现
C语言中的经典算法实现
84 1
|
6月前
|
存储 算法 搜索推荐
【数据结构和算法】--- 基于c语言排序算法的实现(2)
【数据结构和算法】--- 基于c语言排序算法的实现(2)
38 0
|
6月前
|
搜索推荐 算法 C语言
【数据结构和算法】--- 基于c语言排序算法的实现(1)
【数据结构和算法】--- 基于c语言排序算法的实现(1)
43 0