vector+算法sort与list+sort的效率比较,容易写错的地方原因探析

我写的代码:

#include <iostream>
using namespace std;
#include <vector>
#include <list>
#include <algorithm>
int main()
{const int N = 10000000;vector<int> v;list<int> l;for (int i = 0; i < N; i++){v.push_back(i);l.push_back(i);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();l.sort();int end2 = clock();cout << "vector+算法:" << end1 - begin1 << endl;cout << "list+sort:" << end2 - begin2 << endl;
}

运行结果:无论N为多大,上面永远大于下面

老师的代码:

#include <time.h>
#include <iostream>
using namespace std;
#include <list>
#include <vector>
#include <algorithm>int main()
{srand(time(0));const int N = 10000000;vector<int> v;v.reserve(N);list<int> lt2;for (int i = 0; i < N; i++){auto e = rand();v.push_back(e);lt2.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt2.sort();int end2 = clock();cout << "vector sort:" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;
}

运行结果:N较小时,差不多大,N较大时,上面比小面小得多

原因:

快排在最坏情况下的时间复杂度为(n^2),最坏情况对应的是数据有序,我写的代码就是有序数,所有跑出来的结果和老师的无序数相反,快排的平均时间复杂度是(nlgn),快排只有在无序数中排序才有意义

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

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

相关文章

AcWing 5180. 正方形泳池

原题链接&#xff1a;5180. 正方形泳池 - AcWing题库 说实话题解和视频题解都不太好&#xff0c;有点过于复杂了&#xff0c;那就不得不记录一下我看视频题解衍生出的另一个较为简单的思路了。 根据答案形态出发&#xff0c;枚举所有这种形态找出最大值。 可以发现最大的泳池要…

Ubuntu18.04安装gdal3.4

一.依赖关系 所以&#xff0c;安装顺序&#xff1a;SQLite -> Proj -> Gdal

【AFL学习笔记(一)】简单的使用AFL进行漏洞挖掘测试

首先声明一点&#xff0c;ALF都是在Linux系统上运行 本文使用的是Ubuntu 20.4 版本进行演示 Step 1 下载afl-2.52b 官网地址afl2.52b 直接下载地址直接下载地址 下载完成之后在Ubuntu系统上进行解压&#xff1a; tar -afl-2.52b.tgzStep 2 创建测试用例 ①&#xff1a;创…

20 个有代码的 Python 脚本可使您的工作自动化

阿卜杜勒汉南哈桑 说明 在本文中&#xff0c;我们将探讨 20 个 Python 脚本及其代码&#xff0c;它们可以帮助您自动执行各种任务并提高工作效率。无论您是开发人员、数据分析师&#xff0c;还是只是希望简化工作流程的人&#xff0c;这些脚本都能满足您的需求。 目录 1. 简…

【软考-中级】系统集成项目管理工程师-配置管理历年案例

持续更新。。。。。。。。。。。。。。。 目录 2023 上 试题三(20分)2016 下 试题三(17分) 2023 上 试题三(20分) 某公司有自己的质量管理体系&#xff0c;其中配置管理程序已运行多年&#xff0c;由项目经理牵头组建变更控制委员会(CCB)&#xff0c;在创建配置管理环境后&…

数据库 MySql快速导入外部数据库流程

适用于新安装MySql本地没有数据情况 外部MySql数据库文件 任务管理器停用Mysql进程 将外部文件替换本地默认文件即可 重启电脑导入完成。

前端设计模式应应用场景

前端设计模式应应用场景 创建型模式(Creational Patterns)工厂模式单例模式原型模式 行为型模式(Behavioral Patterns)策略模式观察者模式/发布订阅模式迭代器模式状态模式 结构型模式(Structural Patterns)装饰器模式代理模式 创建型模式(Creational Patterns) 处理对象的创建…

填充颜色游戏

无语死了这题。 题目描述 小明最近迷上下面一款游戏。游戏开始时&#xff0c; 系统将随机生成一个 N N 的 正方形棋盘&#xff0c; 棋盘的每个格子都由六种颜色中的一种绘制。在每个步骤中&#xff0c; 玩家选择一种颜色&#xff0c; 并将与左上角连接的所有网格更改为该特…

树控件的使用

目录 1、修改树控件的基础属性&#xff1a; 2、准备图标 &#xff1a; &#xff08;1&#xff09;、ico后缀的图片放入当前文件路径的rc中 &#xff08;2&#xff09;、在Icon中添加资源&#xff0c;导入图片 &#xff08;3&#xff09;、准备HICON图标 &#xff08;4&am…

音频处理到雷达系统:滤波组的多领域应用 | 百能云芯

在电子元器件和电路设计领域&#xff0c;滤波组&#xff08;Filter Bank&#xff09;是一个关键概念&#xff0c;它用于处理和过滤信号&#xff0c;以满足各种应用的需求。云芯将带您深入研究滤波组在元器件中的应用&#xff0c;包括其工作原理、不同类型以及在通信、音频处理和…

qt 读取txt文本内容时,中文乱码

项目场景&#xff1a; 项目中&#xff0c;需要在TF卡中做类似txt阅读器的功能&#xff0c;因为app是在嵌入式系统下运行的&#xff0c;发现当读取txt的文本格式为ANSI时&#xff0c;中文的显示是乱码&#xff0c;故记录下解决方法 问题解决 中文乱码问题还是涉及到编码问题&…

【Unity】Unity开发微信小游戏(一)准备和了解工作

一、所需工具 0.Unity小游戏版本 如不使用此版本&#xff0c;则无法搜索到 InstantGame package 1.Unity插件&#xff1a;InstantGame package 此插件用于处理项目中的贴图、音频、网格、动画、场景等资源文件&#xff0c;保证小程序包体不会过大。 插件可以关联UOS服务&am…

百度智能云推出,国内首个大模型全链路生态支持体系

在10月17日举行的百度世界2023上&#xff0c;百度智能云宣布&#xff0c;百度智能云千帆大模型服务平台已服务17000多家客户&#xff0c;覆盖近500个场景。 同时&#xff0c;新的企业和开发者还正在不断地涌入千帆&#xff0c;大模型调用量高速攀升。平台上既有年龄仅14岁的小…

PAM从入门到精通(五)

接前一篇文章&#xff1a;PAM从入门到精通&#xff08;四&#xff09; 本文参考&#xff1a; 《The Linux-PAM Application Developers Guide》 先再来重温一下PAM系统架构&#xff1a; 更加形象的形式&#xff1a; 五、主要函数详解 3. pam_set_item 概述&#xff1a; 设置…

【定时开关机】windows 10 如何设置定时开关机

一、需求 二、场景 三、思路 四、实现 A. 设置来电开机 B. 设置及定时关机 一、需求 需要一台 win 10 的电脑在工作时间内自动开关机&#xff08;早 8:30 - 晚&#xff1a;6:05&#xff09; 二、场景 开机&#xff1a;早 8:30 关机&#xff1a;晚 6:05 三、思路 【开机…

目标跟踪数据集分享

360VOT: A New Benchmark Dataset for Omnidirectional Visual Object Tracking 360VOT 是一个新的大规模全景追踪基准数据集&#xff0c;旨在为全景视觉物体追踪提供支持。这个数据集包含了 120 个序列&#xff0c;总计超过 11.3 万张高分辨率帧&#xff0c;采用等距投影。追踪…

new Object()到底占用几个字节

Java内存模型 对象内存中可以分为三块区域&#xff1a;对象头(Header)&#xff0c;实例数据(Instance Data)和对齐填充(Padding)&#xff0c;以64位操作系统为例(未开启指针压缩的情况)Java对象布局 如下图所示&#xff1a; 其中对象头中的Mark Word中的详细信息在文章synchr…

李宏毅生成式AI课程笔记(持续更新

01 ChatGPT在做的事情 02 预训练&#xff08;Pre-train&#xff09; ChatGPT G-Generative P-Pre-trained T-Transformer GPT3 ----> InstructGPT&#xff08;经过预训练的GPT3&#xff09; 生成式学习的两种策略 我们在使用ChatGPT的时候会注意到&#xff0c;网站上…

JVM 垃圾回收机制(可达性分析、引用计数)

目录 1 什么是垃圾2 为什么需要回收3 哪些对象被判定为垃圾呢3.1 引用计数法3.2 可达性分析算法&#xff1a;GC Roots根 1 什么是垃圾 垃圾是指在运行程序中没有任何指针指向的对象&#xff0c;就是需要被回收的。 2 为什么需要回收 执行程序会不断地分配内存空间&#xff0c…

Windows安装SNMP服务

windows10安装SNMP服务 打开计算机的设置–应用–应用和功能–可选功能–点击加号添加功能,添加以下两个功能: windows server安装SNMP服务 搜索打开服务器管理器,点击功能–添加功能,勾选SNMP服务,点击下一步,等待安装完成 按win+R快捷键,运行service.msc,在服务中将…