【数据结构】常见复杂度习题详解 ------ 习题篇

文章目录

  • 📋前言
  • 一. ⛳️前篇回顾
  • 二. ⛳️常见时间复杂度计算举例
    • 1️⃣实例一
    • 2️⃣实例二
    • 3️⃣实例三
    • 4️⃣实例四
    • 5️⃣实例五
    • 6️⃣实例六
    • 7️⃣实例七
    • 8️⃣实例八
  • 三. ⛳️常见空间复杂度计算举例
    • 1️⃣实例一
    • 2️⃣实例二
    • 3️⃣实例三
  • 四. ⛳️总结


📋前言

🏠 个人主页:@聆风吟的个人主页

🔥系列专栏:本期文章收录在《数据结构初阶》,大家有兴趣可以浏览和关注,后面将会有更多精彩内容!

⏰寄语:少年有梦不应止于心动,更要付诸行动。
🎉欢迎大家关注🔍点赞👍收藏⭐️留言📝
🌈作者留言:本文从上篇文章《算法、时间复杂度和空间复杂度详解 》中剥离出来的,由于详解和题目放在一起篇幅过长,不利于大家更好吸收知识点,特此将其剥离出来。



一. ⛳️前篇回顾

上篇文章我们主要学习了:

  1. 算法的定义:算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
  2. 算法的特性:有穷性、确定性、可行性、输入、输出。
  3. 算法的设计要求:正确性、可读性、健壮性、高效率和低存储量需求。
  4. 算法的度量方法:事后统计方法、事前分析估算方法。
  5. 推导大O阶
  6. 时间复杂度
  7. 空间复杂度

    你对以上的内容是否还能够全部回忆起来呢?如果你对某部分还有欠缺,请跳转该篇文章《算法、时间复杂度和空间复杂度详解 》进行复习,再配合着下面习题对时间复杂度和空间复杂度进行巩固。预计明天将会更新数据结构新文,大家抓紧时间在复习下前面知识。



二. ⛳️常见时间复杂度计算举例

1️⃣实例一

// 计算Func1的时间复杂度?
void Func1(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

解析:实例1基本操作执行了2N+10次,根据大O阶的推导方法很容易得出:Func1的时间复杂度为O(N)


2️⃣实例二

// 计算Func2的时间复杂度?
void Func2(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);
}

解析:实例二基本操作执行了M+N次,根据大O阶的推导方法得出:

  • 如果题目没有表明 M 和 N 的大小,Func2的时间复杂度为O(M + N)
  • 如果题目明确表明 M 远大于 N ,则 N 的变化对时间复杂度的影响不大,Func2的时间复杂度为O(M)
  • 如果题目明确表明 N 远大于 M ,则 M 的变化对时间复杂度的影响不大,Func2的时间复杂度为O(N)
  • 如果题目明确表明 M 和 N 一样大,则O(M + N)等价于O(2M)或O(2N),Func2的时间复杂度为O(M)O(N)

3️⃣实例三

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

解析:实例3基本操作执行了100次,根据大O阶的推导方法很容易得出:Func3的时间复杂度为O(1)


4️⃣实例四

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

解析:首先我们先来介绍一下库函数strchr作用:在str指向的字符数组中查找是否包含字符characte。因此实例4的基本操作执行最好1次,最坏N次。根据时间复杂度一般看最坏,strchr的时间复杂度为O(N)


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

解析:本题是冒泡排序函数,冒泡排序的思想是:假设数组中有 n 个元素,第一趟执行将会执行 n-1 次交换,将一个元素排好序。第二趟将会执行 n-2 次交换,将将一个元素排好序…依次类推。排好所有元素需要执行 n-1 次,每趟交换的次数分别为(n - 1),(n-2),(n-3),… ,(2),(1)。由此可知,实例5基本操作执行最好n-1次(即数组已经排好序,只需要执行一趟排序判断数组是否已经有序),最坏执行了( n*(n-1) )/2次(即将所有趟交换的次数相加,可以直接使用等差数列求和),通过推导大O阶方法+时间复杂度一般看最坏,BubbleSort的时间复杂度为O(N^2)


6️⃣实例六

// 计算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;elsereturn mid;}return -1;
}

解析:本题是二分查找函数,每次查找将会将范围缩放一半。因此实例6基本操作执行最好1次,最坏O(logN)次。根据时间复杂度一般看最坏,BinarySearch时间复杂度为 O(logN)
在这里插入图片描述


7️⃣实例七

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

解析:本题是一个简单的递归调用, 实例7通过计算分析发现基本操作递归了N次,时间复杂度为O(N)
在这里插入图片描述

8️⃣实例八

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

解析:本题是一个双递归。实例8通过计算分析发现基本操作递归了2n,Fib的时间复杂度为O(2^n)
在这里插入图片描述



三. ⛳️常见空间复杂度计算举例

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

解析: 实例1使用了常数个额外空间,分别是[ end,exchange,i ]。根据大O阶的推导方法很容易得出,BubbleSort空间复杂度为 O(1)


2️⃣实例二

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

解析:实例2动态开辟了N+1个空间,根据大O阶的推导方法很容易得出,Fibonacci空间复杂度为 O(N)


3️⃣实例三

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

解析:实例3递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)
在这里插入图片描述



四. ⛳️总结

     本文通过大量实例讲解常见时间复杂和空间复杂度计算,希望通过这些例子的讲解能够帮助你在以后的学习中能够更加灵活、精确的计算出一个程序的复杂度,方便我们更快的寻找解决一个问题的最优的算法。

     今天的内容就到这里了,你对今天的内容是否有所掌握?如果还有疑问的话请在评论区里多多提问,大家可以一起帮你解决,让我们共同进步。创作不易,如果对你有用的的话点个赞支持下作者,你们的支持是作者创作最大的动力。关注我不迷路,让我们下期不见不散✋✋。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/169659.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

RedHat8升级GLIBC_2.29,解决ImportError: /lib64/libm.so.6: version `GLIBC_2.29

问题背景 在做大模型微调训练时&#xff0c;执行python脚本时出现如下报错&#xff1a; 查看当前服务器版本&#xff0c;确实没有GLIBC_2.29的 strings /lib64/libm.so.6 | grep GLIBC_ GLIBC_2.2.5 GLIBC_2.4 GLIBC_2.15 GLIBC_2.18 GLIBC_2.23 GLIBC_2.24 GLIBC_2.25 GLIB…

【JAVA学习笔记】43 - 枚举类

项目代码 https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter11/src/com/yinhai/enum_ 〇、创建时自动填入版权 作者等信息 如何在每个文件创建的时候打入自己的信息以及版权呢 菜单栏-File-setting-Editor-File and Code Templaters -Includes-输入信…

多继承的实例介绍

一、多继承同名覆盖 子类中的成员与父类中的成员同名问题&#xff0c;通过作用域分辨符&#xff08;&#xff1a;&#xff1a;&#xff09;进行限定类的访问&#xff0c;从而实现对不同类中的同名成员各自赋值。 #include<iostream> using namespace std; class A{//父…

基于SpringBoot的时间管理系统

基于SpringBoot的时间管理系统的设计与实现~ 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBootMyBatis工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 登录界面 管理员界面 用户界面 摘要 基于Spring Boot的时间管理系统是一款功能丰富…

基于国产ARM+FPGA+AD的验证和生产测试自动化

TestStand是一款测试执行软件&#xff0c;可帮助工程师在验证和生产环节加速开发和部署系统。 验证和生产测试自动化 TestStand可借助自身功能特性&#xff0c;实现用户所有测试系统中整个测试过程的自动化、提速和标准化: 调用和执行使用LabVIEW、Python、C/C或.NET编写的测…

Mybatis 简介(一)

这里使用的是3.5.11版本 MyBatis 是一款优秀的持久层框架&#xff0c;它支持自定义 SQL、存储过程以及高级映射。MyBatis 免除了几乎所有的 JDBC 代码以及设置参数和获取结果集的工作。MyBatis 可以通过简单的 XML 或注解来配置和映射原始类型、接口和 Java POJO&#xff08;P…

基于深度学习网络的手势识别算法matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 clc; clear; close all; warning off; addpath(genpath(pwd)); rng(default)load gnet.mat[Pr…

决策树完成图片分类任务

数据集要求&#xff1a; 训练集 和 验证集 &#xff08;要求分好&#xff09; 图片放置规则 &#xff1a; 一个总文件夹 放类别名称的子文件夹 其中子文件夹 为存放同一类别图片 举个例子 分类动物 则 总文件夹名称为动物 子文件夹为 猫 狗 猪猪 。。。 其中猫的文件夹里面…

IK分词器如何修改支持跨版本ES

一、问题描述&#xff1a;IK分词器版本和ES版本不一致&#xff0c;无法找到和自己ES版本匹配的分词器。 IK分词器&#xff0c;提供的插件版本&#xff0c;远赶不上ES的更新版本&#xff0c;在使用过程中&#xff0c;不一定能顺利的找到与自己使用的ES版本相对应。在ES集群中使用…

C++ string 类的其他操作

4.3.2 string 类的其他操作 在C新增string类之前,程序员也需要完成诸如给字符串赋值等工作。对于C语言式的字符串,程 序员使用C语言库中的函数来完成这些任务。头文件cstring(以前为string.h)提供了这些函数。例如,可 以使用函数 strcpy()将字符串复制到字符数组中,使用函数…

QTday05(TCP的服务端客户端通信)

实现聊天室功能 服务端代码&#xff1a; pro文件需要导入 network 头文件&#xff1a; #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTcpServer>//服务端 #include <QTcpSocket>//客户端 #include <QList> #include <QMes…

Adobe产品2024

一、软件下载&#xff1a; http://dt4.8tupian.net/2/29913a1b2000.pg3二、软件介绍&#xff1a; Adobe公司旗下的产品在影视后期、平面设计等领域有着无可取代的地位。在创意和设计领域中&#xff0c;产品有多达 21 个&#xff0c;包括 Photoshop、Illustrator、InDesign、P…

【软件教程】如何用C++交叉编译出能在Android运行的ELF程序或so动态库

一、配置NDK交叉编译平台 1. 打开Android的官方ndk下载链接https://developer.android.com/ndk/downloads?hlzh-cn&#xff0c;下载windows 64位ndk环境包。 2. 解压后将具有以下文件的路径加入到系统环境变量。 3. 配置好环境变量&#xff0c;如下图所示&#xff0c;Path中存…

使用GoogleNet网络实现花朵分类

一.数据集准备 新建一个项目文件夹GoogleNet&#xff0c;并在里面建立data_set文件夹用来保存数据集&#xff0c;在data_set文件夹下创建新文件夹"flower_data"&#xff0c;点击链接下载花分类数据集https://storage.googleapis.com/download.tensorflow.org/exampl…

推荐几个程序员必逛的个人技术博客网站

1、美团技术团队 地 址: 美团技术团队简 介&#xff1a;美团技术团队的博客&#xff0c;干货满满。推荐指数&#xff1a;⭐⭐⭐⭐⭐ ​ 2、阮一峰的网络日志 地 址: 阮一峰的个人网站 - Ruan YiFengs Personal Website简 介&#xff1a;大神阮一峰&#xff0c;博客风格真正…

PHP 在线考试管理系统mysql数据库web结构layUI布局apache计算机软件工程网页wamp

一、源码特点 PHP 在线考试管理系统是一套完善的web设计系统 layUI技术布局 &#xff0c;对理解php编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。 PHP 在线考试系统1 代码 https://download.csdn.net/download/qq_41…

【31】c++设计模式——>模板方法模式

模板方法模式通常由以下几个部分组成&#xff1a; 1.抽象基类&#xff08;Abstract Base Class&#xff09;&#xff1a;抽象基类定义了一个算法的骨架&#xff0c;其中包含了模板方法和一些基本操作方法。模板方法在抽象基类中被声明为虚函数&#xff0c;它定义了算法的流程&…

制作macOS Ventura U盘启动盘教程

macOS 14更新一段时间了&#xff0c;发现某些应用不适配想要无损降级&#xff0c;如何进行macOS的降级呢&#xff0c;除了备份好的时间机器备份&#xff0c;还需要一个可以引导的macOS U盘安装器&#xff0c;如何制作macOS 13 Ventura 系统启动U盘呢&#xff0c;小编带来对新手…

线性表操作的实现--顺序表

本文参考朱战力老师的数据结构与算法--使用C语言一书 文章目录 前言 一、线性表是什么&#xff1f; 二、具体实现 1.顺序表的定义 2.初始化ListInitiate&#xff08;L&#xff09; 3.求当前元素个数ListLength&#xff08;L&#xff09; 4.插入元素ListInsert&#xff08;L&…

Ubuntu deadsnakes 源安装新版 python

前言 适用于 Ubuntu 安装 python3.11 等新版本。 因为比较常用并且不想重新编译就记录一下&#xff0c;方便以后面向CV安装。 安装 添加 deadsnakes ppa 源 sudo add-apt-repository ppa:deadsnakes/ppa更新 apt sudo apt update安装 python3.11 sudo apt install python…