身家过亿的帝都富豪对小码农说你时空复杂度会了吗

简介: 身家过亿的帝都富豪对小码农说你时空复杂度会了吗

文章目录


被富豪注意了,我赶紧写下时空复杂度这篇文章

联动文章 身价过亿的女王对小码农说中断会了吗

什么是数据结构

就是实现一些项目,需要在内存中将数据存储起来


算法的时间复杂度和空间复杂度

1.算法效率

2.时间复杂度

3.空间复杂度

4.常见的时间复杂度以及复杂度oj练习


1.算法效率

如何衡量一个算法的好坏

比如下面的斐波那契数列

long long Fib(int N)
{
    if(N < 3)
      return 1;
    return Fib(N-1) + Fib(N-2);
}

算法的复杂度

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

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

时间复杂度

时间复杂度的概念

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

注意:

1.这里的函数是数学中带有未知数的函数表达式,

2.并且我们说的时间不是秒,而是几次几次的意思

因为机器不同(有的2核,有的一核),具体的运行时间就不同,所以没办法用时间来衡量时间复杂度

// 请计算一下Func1中++count语句总共执行了多少次?
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--)
        {
            ++count;
        }
    printf("%d\n", count);
}

image.png

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。

大O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号。

推导大O阶方法:

1.用常数1取代运行时间中的所有加法常数

2.在修改后的运行次数函数中,只保留最高阶项。

3.如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶

另外有些算法的时间复杂度存在最好,平均和最坏情况

==最坏情况:==任意输入规模的最大运行次数(上界)

==平均情况:==任意输入规模的期望运行次数

==最好情况:==任意输入规模的最小运行次数(下届)

在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

实例

例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);
}

image.png

例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);
}

image.png

例3

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

image.png

例4

// 计算strchr的时间复杂度?
const char* strchr(const char* str, int character);

image.png

例5

#include<stdio.h>
// 计算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;
  }
}

image.png

例6

算时间复杂度不能只去看几层循环,而要去看他的思想

// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{
  assert(a);
  int begin = 0;
  int end = n - 1;
  while (begin < end)
  {
    int mid = begin + ((end - begin) >> 1);
    if (a[mid] < x)
      begin = mid + 1;
    else if (a[mid] > x)
      end = mid;
    else
      return mid;
  }
  return -1;
}

image.png

例7

#include<stdio.h>
// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{
  if (0 == N)
    return 1;
  return Fac(N - 1) * N;
}

image.png

例8

我们要知道时间复杂度的时间是不复用的

#include<stdio.h>
// 计算斐波那契递归Fib的时间复杂度?
long long Fib(size_t N)
{
  if (N < 3)
      return 1;
  return Fib(N - 1) + Fib(N - 2);
}

image.png


空间复杂度

空间复杂度也是一个数学表达式,是对一个算法在运行过程中==临时占用额外存储空间大小的量度 。==空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法

注意

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


实例

例1

#include<stdio.h>
// 计算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;
  }
}

image.png

例2

#include<stdio.h>
// 计算Fibonacci的空间复杂度?
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
  if (n == 0)
    return NULL;
  long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
  fibArray[0] = 0;
  fibArray[1] = 1;
  for (int i = 2; i <= n; ++i)
  {
    fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
  }
  return fibArray;
}

image.png

例3

栈帧的消耗看递归的深度

#include<stdio.h>
// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{
  if (N == 0)
    return 1;
  return Fac(N - 1) * N;
}

image.png

栈并不是很大

image.png

例4

空间是可以重复利用,不累计的。时间是不复用的,累计的。这句话是时间复杂度,空间复杂度的精髓

#include<stdio.h>
// 计算斐波那契递归Fib的空间复杂度?
long long Fib(size_t N)
{
  if (N < 3)
      return 1;
  return Fib(N - 1) + Fib(N - 2);
}

image.png

常见的复杂度对比

image.png


复杂度的OJ练习

1.消失的数字

image.png

**思路一:**这道题很多人想法就是排序然后从小到大再去遍历 qsort快排–》时间复杂度O(N*log2N),明显不满足条件

**思路二:**这个思路和数组下标联合起来了,数组用的好基本也是奇计,(0+1+2+…+n)-(nums[0]+nums[1]+nums[2]+…+nums[n-1])

image.png

**思路三:**还有就是很类似上面那个思路,创建一个(n+1)数组

image.png

**思路四:**谷歌面试题考过类似的 创建一个变量x=0,让x与[0,n]全都异或一遍,再和,数组里面的异或一遍,然后再后个数异或一遍,最后得到的x就是我们缺的数 我们知道两个相同的数异或就没了

image.png

2.旋转数组

image.png

你们发现了吗哈哈思路一永远都是高校学生的做法,永远都是暴力求解,简单粗暴法

**思路一:**暴力求解旋转k次 时间复杂度是O(N*K) 空间复杂度O(1)

**思路二:**开辟额外的空间,用空间来换取时间,这也是比较好的方法 时间复杂度O(N) 空间复杂度O(N),但是不符合题目要求,空间超过了

**思路三:**很牛逼,在《程序员的基本修养》上面好像有这道题三步翻转,前面翻转,后面翻转,然后整体翻转大牛想出的高效方法

时间复杂度O(N) 空间复杂度O(1)

image.png

联动文章 身价过亿的女王对小码农说中断会了吗


目录
相关文章
数据敏感度是个什么鬼? by彭文华
数据敏感度是个什么鬼? by彭文华
|
3月前
|
SQL 存储 Oracle
"挑战极限!Oracle数据库精英试炼场:夺命连环5问,你能否一路披荆斩棘,登顶技术巅峰?"
【8月更文挑战第9天】Oracle,数据库领域的巨擘,以卓越的数据处理能力、稳定性和安全性成为企业级应用首选。今天我们带来“Oracle夺命连环25问”。首问:核心组件有哪些?答:实例(含内存结构和后台进程)、物理存储(数据文件、控制文件等)及逻辑存储(表空间、段等)。第二问:如何理解事务隔离级别?答:Oracle支持四种级别,默认READ COMMITTED,避免脏读,但可能遇到不可重复读和幻读。
45 0
|
5月前
1032 挖掘机技术哪家强 (20 分)
1032 挖掘机技术哪家强 (20 分)
1032 挖掘机技术哪家强 (20 分)
为了用事实说明挖掘机技术到底哪家强,PAT 组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。
124 0
|
Web App开发 编解码 缓存
乾坤之大,一锅炖不下
qiankun 源码学习什么是乾坤乾为天,坤为地,乾坤代表天地。不得不说这个名字:qiankun 是基于 single-spa 的微前端解决方案。什么是微前端?什么是 single-spa?前端喜欢不断的造轮子这件事儿是毋庸置疑的,但轮子都有被造出来的原因,比如 single-spa,他是最早的微前端框架。微前端产生的原因很多:拆分巨石应用/集成其他应用(可能技术栈不同)/各前端模块独立开发部署.
358 0
乾坤之大,一锅炖不下
|
编译器 Linux 程序员
身价过亿的帝都富豪对小码农说预处理学的不错
身价过亿的帝都富豪对小码农说预处理学的不错
178 0
身价过亿的帝都富豪对小码农说预处理学的不错
|
存储 Linux
身价过亿的帝都富豪对小码农说顺序表会了吗
身价过亿的帝都富豪对小码农说顺序表会了吗
146 0
身价过亿的帝都富豪对小码农说顺序表会了吗
|
安全 测试技术 区块链
深入探访支付宝双11十年路,技术凿穿焦虑与想象极限 | CYZONE特写
支付宝与欲望、想象力的博弈乃至搏斗,10年来不曾停歇。
3337 0