首页 > 编程语言 >c++ day 8

c++ day 8

时间:2023-07-12 22:12:12浏览次数:42  
标签:arr 递归 int 复杂度 c++ 算法 数组 day

今天终于来学习时间复杂度了

当分析算法的时间复杂度时,我们通常关注以下几个方面来确定算法的执行时间:

    1. 循环次数:循环是算法中常见的结构,它会重复执行一段代码。时间复杂度取决于循环的次数。例如,一个循环从1到n的遍历,时间复杂度就是O(n)。

    2. 嵌套循环:如果算法中存在多个嵌套循环,我们需要考虑每个循环的迭代次数。例如,一个包含两个嵌套循环的算法,外层循环迭代n次,内层循环迭代m次,那么总的时间复杂度就是O(n * m)。

    3. 递归调用:递归算法通过自身的调用来解决问题。递归的时间复杂度取决于递归调用的次数以及每次递归的规模。例如,二分查找算法的时间复杂度为O(log n),其中n是输入规模。

    4. 条件判断和分支:条件判断语句(如if语句)的执行次数会影响算法的时间复杂度。例如,如果一个算法的执行路径取决于输入数据的特定情况,我们需要考虑每个条件判断的执行次数。

    5. 数据结构操作:算法中的数据结构操作,如插入、删除、查找等,对算法的时间复杂度产生影响。不同的数据结构具有不同的操作复杂度。例如,在一个数组中查找特定元素的时间复杂度为O(n),而在一个二叉搜索树中查找的时间复杂度为O(log n)。

说实话 感觉不好去理解

下面我将会从几个例子去理解

一个常见的例子是计算数组中所有元素的和。假设有一个包含n个整数的数组,我们的目标是计算出这些整数的总和。

下面我将展示两种算法的例子,并解释它们的时间复杂度。

  1. 算法一:迭代求和
int sum = 0;
for (int i = 0; i < n; i++) {
    sum += arr[i];
}

这个算法使用一个循环遍历数组中的每个元素,并将它们相加得到最终的总和。在这种情况下,循环的次数与数组的大小n相等,因此循环的时间复杂度是O(n)。这是一种线性时间复杂度。

  1. 算法二:递归求和
int sumArray(int arr[], int start, int end) {
    if (start == end) {
        return arr[start];
    } else {
        int mid = (start + end) / 2;
        int leftSum = sumArray(arr, start, mid);
        int rightSum = sumArray(arr, mid + 1, end);
        return leftSum + rightSum;
    }
}

int sum = sumArray(arr, 0, n - 1);

这个算法使用递归来分治地计算数组的总和。它将数组划分为两半,并递归地计算每个子数组的总和,然后将它们相加得到最终结果。在这个算法中,每次递归调用都将数组的规模减半,因此递归的时间复杂度是O(log n)。这是一种对数时间复杂度。

通过比较这两个算法,我们可以看到第一个算法具有线性时间复杂度O(n),而第二个算法具有对数时间复杂度O(log n)。因此,第二个算法在处理大型输入时比第一个算法更高效。

下一个例子是

二分查找:假设有一个已排序的数组,我们要在其中查找特定的元素。二分查找是一种高效的算法,其时间复杂度为O(log n)。

int binarySearch(int arr[], int target, int left, int right) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}
在每次迭代中,二分查找将搜索范围减半,直到找到目标元素或确定目标元素不存在。因此,它的时间复杂度为O(log n),其中n是数组的大小。
冒泡排序:冒泡排序是一种简单但效率较低的排序算法。它的时间复杂度为O(n^2)。
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换相邻元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

冒泡排序通过多次遍历数组,比较相邻元素并交换它们的位置来实现排序。在最坏的情况下,每个元素都需要与其他元素比较和交换,因此它的时间复杂度为O(n^2)。

 

标签:arr,递归,int,复杂度,c++,算法,数组,day
From: https://www.cnblogs.com/jszs0013/p/17549003.html

相关文章

  • Java学习day02:流程控制1
    我在B站上大学......
  • HTML-DAY01
    1.前端三剑客之一——HTML(超文本标记语言)什么是HTMLHyperTextMarkupLanguage超文本标记语言,体现可以对文本进行标记(颜色/字体大小),并且对动画,图片进行渲染等等!2.页面标准结构介绍<!DOCTYPEhtml>html5的文档类型<html>html的标准的开始标签<head>头标签<metac......
  • nestjs入门学习 | day2
    nestjs入门学习|day2day2:nest基础知识点学习:中间件、异常过滤器、守卫、管道、拦截器中间件Nest中间件可以是一个函数,也可以是一个带有@Injectable()装饰器的类,且该类应该实现NestMiddleware接口,而函数没有任何特殊要求。如下是一个日志中间件的简单示例:import{......
  • nestjs入门学习 | day1
    nestjs入门学习|day1day1:为什么要用nestjs,和egg区别对比nest项目初始化,了解目录结构nestcli命令了解nest基础知识点学习:控制器、服务、模块为什么要用nestjs,和egg区别对比官网介绍Nest提供了一种开箱即用的应用程序架构,允许开发人员和团队创建高度可测试、可扩展......
  • 你省(福建)省队集训 Day5 T3 乱搞分析
    简要题意有\(1\leT\le10^6\)次询问,每次询问正整数\(x,p\),\(p\)为素数,令\(n=xp^2\),问是否存在三个正整数\(a,b,c\),满足\(ab+bc+ca=n\)。有的话给出构造,否则输出\(-1\)。solution打表注意到只有\(n=4,18\)是无解的。打表namespaceDB{ constintN=1e5; struc......
  • python基础day43
    约束条件约束条件:在数据类型的基础上再添加限制条件1.unsigned去除符号createtablet1(idintunsigined);2.zerofill用0填充createtablet2(idintzerofill);3.notnull非空createtablet3(idint,namevarchar(16));createtabl......
  • Day03-15 方法
    1、何谓方法?Java方法是语句的集合,它们在一起执行一个功能。方法是解决一类问题的步骤的有序组合方法包含于类或对象中方法在程序中被创建,在其他地方被引用设计方法的原则方法的本意是功能块,就是实现某个功能的语句块的集合。我们设计方法的时候,最好保持方法的原......
  • Day08(2023.07.12)
    行程8:45    到达上海市信息安全测评认证中心(黄浦区陆家浜路1308号)9:00  学习《网络安全等级测评师培训教材》11:30--13:00   吃饭休息13:00 学习《网络安全等级测评师培训教材》17:00      下班 路由器:堡垒机:如......
  • day3
    一、简单的图片1.得到png,zsteg分析发现特殊文本2.zsteg导出zsteg-aIM.png-Eb1,bgr,lsb,xy>1.txt,发现字符在xsctf之间,猜测分别对应的就是0、1、2、3、4,转换一下3.猜测是5进制数,转化一下十进制再转化为字符串,写个脚本点击查看代码importmathls=['00402','0041......
  • 【C++开源库】Windows 下编译 libcurl 库
    Whatislibcurl?libcurl是一个跨平台的网络协议库,支持http,https,ftp,gopher,telnet,dict,file,和ldap协议。libcurl同样支持HTTPS证书授权,HTTPPOST,HTTPPUT,FTP上传,HTTP基本表单上传,代理,cookies和用户认证。想要知道更多关于libcurl的介绍,可以到官网......