学习数据结构:算法的时间复杂度和空间复杂度

这篇具有很好参考价值的文章主要介绍了学习数据结构:算法的时间复杂度和空间复杂度。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、算法的复杂度

衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。

算法的时间复杂度

算法中的基本操作的执行次数,为算法的时间复杂度。

算法的空间复杂度

空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

 时间复杂度和空间复杂度都是由大O的渐近表示法来表示

推导大O阶方法:
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

 二、常见复杂度对比

学习数据结构:算法的时间复杂度和空间复杂度,数据结构C语言版,数据结构,学习

学习数据结构:算法的时间复杂度和空间复杂度,数据结构C语言版,数据结构,学习

 三、常见的时间复杂度和空间复杂度的计算

一、时间复杂度计算举例

// 计算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);
}

 O(N*2+10),Func2的时间复杂度为O(N)

// 计算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);
}

O(M+N),若M>>N 则时间复杂度为 O(M),反之则为O(N).

              若M==N则时间复杂度为O(N)或O(M).

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

 O(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;
}
}

O((N+1)*(N)/2)   时间复杂度为O(N^2)

// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
// [begin, end]:begin和end是左闭右闭区间,因此有=号
while (begin <= end)
{
int mid = begin + ((end-begin)>>1);
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid-1;
else
return mid;
}
return -1;
}

二分查找  O(logn);ps:logN在算法分析中表示是底数为2,对数为N。

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

O(N)

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

学习数据结构:算法的时间复杂度和空间复杂度,数据结构C语言版,数据结构,学习

 O(logN)

 二、空间复杂度计算举例

// 计算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;
}
}

空间复杂度O(1),开了常数个

// 计算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;
}

O(N)

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

O(N)

四、复杂度的oj练习

一、消失的数字

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode-cn.com/problems/missing-number-lcci学习数据结构:算法的时间复杂度和空间复杂度,数据结构C语言版,数据结构,学习

大家看这道题是不是感觉有些熟悉呢??

有没有想到之前的那个单身狗问题呢?

这个题也跟那个题类似,先定义一个int类数,然后先与n个数异或,再与数组中的数异或

最后这个数就是数组中缺少的值.

因为1^1=0

int missingNumber(int* nums, int numsSize){
  int num=0;
  for(int i=0;i<=numsSize;i++){
    num^=i;
  }
  for(int i=0;i<numsSize;i++){
    num^=nums[i];
  }
  return num;
}
int missingNumber(int* nums, int numsSize){
  int num=0;
  for(int i=0;i<=numsSize;i++){
    num+=i;
  }
  for(int i=0;i<numsSize;i++){
    num-=nums[i];
  }
  return num;
}

二、旋转数组

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode-cn.com/problems/rotate-array学习数据结构:算法的时间复杂度和空间复杂度,数据结构C语言版,数据结构,学习

 这个题有两种思路:

思路一:先将n-k个逆置,再将后k个逆置,最后直接整体逆置。(妙啊!!!)

void rotate(int* nums, int numsSize, int k) {
    k%=numsSize;
    int tmp[numsSize];
    int n=numsSize;
    memcpy(tmp,nums+n-k,sizeof(int)*k);
    memcpy(tmp+k,nums,sizeof(int)*(n-k));
    memcpy(nums,tmp,sizeof(int)*(n));
}

 

void Reverse(int*a,int left,int right){
    int tmp=a[left];
    a[left]=a[right];
    a[right]=tmp;
    right--;
    left++;
}
void rotate(int* nums, int numsSize, int k) {
    k%=numsSize;
    //[0,numssize-k-1]
   Reverse(nums,0,numsSize-k-1);
   //[numssize-k,numssize-1]
   Reverse(nums,numsSize-k,numsSize-1);
   Reverse(nums,0,numsSize-1);
}
今天的内容就到此位置了,谢谢各位大佬观看!!!

学习数据结构:算法的时间复杂度和空间复杂度,数据结构C语言版,数据结构,学习文章来源地址https://www.toymoban.com/news/detail-847886.html

到了这里,关于学习数据结构:算法的时间复杂度和空间复杂度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构和算法】时间复杂度和空间复杂度

    目录   一、前言 二、时间复杂度 2.1时间复杂度表示形式 2.1.1规则: 3.1如何计算时间复杂度 3.1.1线性阶 3.1.2平方阶 3.1.3对数阶 常见的时间复杂度排序: 三、空间复杂度 3.1Java的基本类型内存占用 数据结构和算法是程序的灵魂,这是某位程序员大佬所言,学习了这门,我们便可

    2023年04月09日
    浏览(48)
  • 数据结构与算法-时间复杂度与空间复杂度

    数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 算法就是定义良好的计算过程,他取一个或一组的值为输入,并产生一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。 算法在

    2024年02月07日
    浏览(49)
  • 数据结构与算法—时间复杂度和空间复杂度

    目录 1、什么是数据结构? 2、什么是算法? 3、算法的复杂度 4、时间复杂度 (1) 时间复杂度的概念:  (2) 大O的渐进表示法:  六个例题: (3) 时间复杂度对比:  三个例题:  OJ题分析时间复杂度 5、空间复杂度 (1)常见复杂度对比  (2)OJ题分析空间复杂度 小结 数据结构 (D

    2024年02月07日
    浏览(92)
  • 数据结构--算法的时间复杂度和空间复杂度

    算法效率是指 算法在计算机上运行时所消耗的时间和资源 。这是衡量算法执行速度和资源利用情况的重要指标。 例子: 这是一个斐波那契函数,用的是递归的计算方法,每次创建函数就会在栈区开辟一块空间,递归次数越多,开辟空间越多; 所以, 代码的简洁说明不了算

    2024年02月15日
    浏览(49)
  • 算法的时间复杂度和空间复杂度(数据结构)

    目录 1、算法效率 1如何衡量一个算法的好坏 2算法的复杂度 2、时间复杂度 1时间复杂度的概念 2大O的渐进表示法 2时间复杂度计算例题 1、计算Func2的时间复杂度 2、计算Func3的时间复杂度 3、计算Func4的时间复杂度 4、计算strchr的时间复杂度 5、计算BubbleSort的时间复杂度 6、计算

    2024年02月03日
    浏览(68)
  • 【数据结构与算法】1.时间复杂度和空间复杂度

    📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点,相互学习进步! 算法效率分为两种:第一种是时间效率;第二种是空间效率。时间效率又称为时间

    2024年01月20日
    浏览(54)
  • 数据结构 | 算法的时间复杂度和空间复杂度【详解】

    数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 算法(Algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转

    2024年02月08日
    浏览(57)
  • 【数据结构与算法篇】时间复杂度与空间复杂度

       目录 一、数据结构和算法 1.什么是数据结构?  2.什么是算法? 3.数据结构和算法的重要性 二、算法的时间复杂度和空间复杂度 1.算法效率 2.算法的复杂度 3.复杂度在校招中的考察 4.时间复杂度 5.空间复杂度  6.常见复杂度对比 7.复杂度的OJ练习   👻内容专栏:《数据结

    2023年04月24日
    浏览(67)
  • 数据结构练习-算法与时间复杂度

    -----------------------------------------------------------------------------------------------------------------------------          1. 设n是描述问题规模的非负整数,下列程序段的时间复杂度是( )。         A.O(logn) B.O(n^(1/2)) C.O(n) D.O(n²)         解析:         分析选项 A. O(log n) :这通常描

    2024年04月25日
    浏览(59)
  • 【数据结构初阶】算法的时间复杂度和空间复杂度

    1.1 如何衡量一个算法的好坏 如何衡量一个算法的好坏呢? 比如对于以下斐波那契数列: 斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何衡量其好与坏呢? 1.2 算法的复杂度 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此

    2024年02月08日
    浏览(75)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包