1.算法——数据结构学习

算法是解决特定问题求解步骤的描述。

从1加到100的结果

# include <stdio.h>  int main(){  int i, sum = 0, n = 100;   // 执行1次for(i = 1; i <= n; i++){  // 执行n + 1次sum = sum + i;    // 执行n次}  printf("%d", sum); // 执行1次return 0;  
}

高斯求和

# include <stdio.h>  int main(){  int sum = 0, n = 100;   // 执行1次sum = (1 + n) * n / 2;  // 执行1次printf("%d\n", sum);  // 执行1次return 0;  
}

概念

算法的定义

解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

算法的特性

  • 输入输出
    • 具有零个或多个输入
    • 至少有一个或多个输出
  • 有穷性
    • 执行有限步骤后会自动结束
    • 每个步骤在可接受的时间内完成
  • 确定性
    • 每一步骤具有确定的含义
    • 无二义性
  • 可行性
    • 每一步都必须是可行的,能在有限步内完成

算法的设计要求

  • 正确性
    • 算法程序没有语法错误
    • 算法程序对于合法的输入数据能够产生满足要求的输出结果
    • 算法程序对于非法的输入数据能够得出满足规格说明的结果
    • 算法程序对于精心选择的,甚至刁难的测试数据都有满足要求的输出结果
  • 可读性
  • 健壮性
  • 时间效率高,存储量低

算法的度量方法

事后统计法

通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低。

缺点:

  • 必须依据算法事先编制好程序,需要花费大量时间和精力,若编制出发现是个很糟糕的算法,竹篮打水一场空
  • 时间的比较以来计算机硬件和软件等环境因素,有时会掩盖算法本身的优劣
  • 算法的测试数据设计困难,程序运行时间往往与数据的规模有很大关系,效率高的算法在小的测试数据面前得不到体现

事前分析估算法

在计算机程序编制前,依据统计方法对算法进行估算。

一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于:

  1. 算法采用的策略和方法 —> 算法好坏的根本
  2. 编译产生的代码质量 —> 由软件支持
  3. 问题的输入规模
  4. 机器执行指令的速度 —> 硬件性能
    一个程序的运行时间,依赖于算法的好坏和问题的输入规模(输入量)。

两种求和算法

# include <stdio.h>  int main(){  int i, sum = 0, n = 100;   // 执行1次for(i = 1; i <= n; i++){  // 执行n + 1次sum = sum + i;    // 执行n次}  printf("%d", sum); // 执行1次return 0;  
}

2n+3次

# include <stdio.h>  int main(){  int sum = 0, n = 100;   // 执行1次sum = (1 + n) * n / 2;  // 执行1次printf("%d\n", sum);  // 执行1次return 0;  
}

3次

延展

# include <stdio.h>  int main() {  int i, j, x = 0, sum = 0, n = 100;  // 执行一次  for(i = 1; i <= n; i++){  for (j = 1; j <= n; j++){  x++;  // 执行n×n次  sum = sum + x;  }  }  printf("%d", sum);  // 执行一次  return 0;  
}

测定运行时间最可靠的方法就是计算对运行时间有消耗的的基本操作的执行次数。

  • 不计循环索引的递增、循环终止条件、变量声明、打印结果等操作

  • 分析程序的运行时间时,最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤

  • 分析一个算法的运行时间,重要的是把基本操作的数量和输入规模关联起来,即基本操作的数量必须表示成输入规模的函数


函数的渐近增长

给定两个函数f(n)和g(n),若存在一个整数N,使得对于所有n>N,f(n)总是比g(n)大,那么我们说f(n)的增长渐近快于g(n)

  • 可以忽略加减常数
  • 与最高次项相乘的常数并不重要
    判断一个算法的效率时,函数中的常数和其他次要项常常可忽略,而更应该关注最高阶项的阶数。

某个算法,随着n的增大,它会越来越优于另一算法或越来越差于另一算法。


算法的时间复杂度

进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。

  • 算法的时间复杂度,也就是算法的时间度量,记作T(n)=O(f(n)) —> 大O记法
  • 它随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称:时间复杂度
  • f(n)是问题规模n的某个函数

增长最慢的算法为最优算法。
图片来源:《数据结构 C++版》邓俊辉著

推导大O阶方法

  1. 用常数1取代运行时间中的所有加法常数
  2. 在修改后的运行次数中函数中,只保留最高阶项
  3. 如果最高阶项存在且系数不是1,则去除与这个项相乘的系数

常数阶 O(1)

顺序结构的时间复杂度。
执行时间恒定的算法:O(1)的时间复杂度 —> 常数阶

不论常数为多少,都记作O(1)!

对于分支结构而言,无论真假,执行的次数都是恒定的,不会随着n的变大而发生变化,单纯的分支结构 -> 复杂度也为O(1)

线性阶 O(n)

线性阶的循环结构。
要确定某个算法的阶数,常需要确定某个特定语句或某个语句集的运行次数。

分析算法的复杂度,关键就是要分析循环结构的运行情况!

int i;  
for(i = 0; i < n; i++){  // 时间复杂度为O(1)的程序步骤序列  
}

对数阶 O(logn)

int count = 1;  
while (count < n){  count = count * 2;  // 时间复杂度为O(1)的程序步骤序列  
}

每次count乘2后,离n就近一分, 2 x = n , x = log ⁡ 2 n 2^x=n,x=\log_{2}n 2x=n,x=log2n

平方阶 O( n 2 n^2 n2)

int i,j;  
for(i = 0; i < n; i++){  for(j = 0; j < n; j++){  // 时间复杂度为O(1)的程序步骤序列  }  
}

循环的时间复杂度等于循环体的复杂度乘以该循环的次数。

理解大O阶推导不算难,难的是对数列的一些相关运算,更多的是考察数学知识和能力!特别是数列方面的知识和解题能力!

常见时间复杂度表
图片来源:《大话数据结构》程杰著


最坏与平均情况

最坏情况是一种保证,通常我们提到的运行时间都是最坏情况的运行时间。

平均运行时间是所有情况中最有意义的,因为它是期望的运行时间。


算法空间复杂度

计算公式:S(n)=O(f(n))
n -> 问题的规模,f(n)为语句关于n所占存储空间的函数

一般情况,一个程序在机器上执行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。

通常使用“时间复杂度”指运行时间的需求;使用“空间复杂度”指空间需求。
不用限定词地使用“复杂度”时,通常指:时间复杂度

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

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

相关文章

vue3 - 按需导入使用Element Plus图标、iconify图标、本地SVG/PNG图标

GitHub Demo 地址 在线预览 vue3 - 按需导入使用Element Plus图标、iconify图标、本地SVG/PNG图标 [GitHub Demo 地址](https://github.com/iotjin/jh-vue3-admin)[在线预览 ](https://iotjin.github.io/jh-vue3-admin) 一、iconify插件安装使用效果图 二、通过自动导入使用ic…

基于微信小程序的音乐播放器设计与实现(源码+lw+部署文档+讲解等)

前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb;…

在虚拟机上安装win10/ubuntu的教程

以下内容源于网络资源的学习与整理&#xff0c;如有侵权请告知删除。 一、下载软件资源 1、首先下载虚拟机Vmware_Pro17软件并正确安装&#xff1a;网盘链接 2、然后下载操作系统的镜像文件&#xff1a;MSDN, 我告诉你 - 做一个安静的工具站 二、在虚拟机上安装ubuntu系统 1…

共享门店模式:一种新兴的商业模式

共享门店模式是一种利用实体店铺的空间和资源&#xff0c;让多个品牌或商家在同一地点共同运营的商业模式。这种模式可以提高店铺的利用率&#xff0c;降低经营成本&#xff0c;增加客流量&#xff0c;实现资源的最大化利用。如果你是一个有创业想法的企业家&#xff0c;或者你…

2023-9-26 JZ52 两个链表的第一个公共节点

题目链接&#xff1a;两个链表的第一个公共节点 import java.util.*; /* public class ListNode {int val;ListNode next null;ListNode(int val) {this.val val;} }*/ public class Solution {public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {ListNo…

数据统计和分析怎么做?spss如何做好数据分析?

为什么要做数据分析?数据分析有什么意义&#xff1f;数据分析可以为企业和组织提供多方面的帮助&#xff0c;包括提高工作效率、优化业务流程、升职加薪、提高管理效率以及改进汇报效果等方面。 IBM SPSS Statistics 26是一款功能强大的统计分析软件&#xff0c;适用于Mac操作…

LabVIEW风力涡轮机的雷电流测量系统中集成高速摄像机

LabVIEW风力涡轮机的雷电流测量系统中集成高速摄像机 随着全球风电装机容量的快速增长&#xff0c;雷电活动对风力发电机组造成的损害受到更多关注&#xff0c;特别是在雷电活动强烈的地区。在冬季闪电期间&#xff0c;风力涡轮机等高层结构会受到向上的雷击。众所周知&#x…

JetBrains 产品安装插件(plugins)的两种方式

安装分为在线、离线两种方式&#xff1a; 在线方式&#xff1a; File > Settings > Plugins 搜索插件 Install 即可 离线方式&#xff1a; 官网&#xff1a;https://plugins.jetbrains.com/ 搜索到插件后&#xff0c;点击 "Get"&#xff0c;选择自己安装的…

maven本地安装jar包

在实际开发中&#xff0c;有些jar包不能通过公共库下载&#xff0c;只能本地安装。可以按照以下步骤操作&#xff1a; 1、安装命令 mvn install:install-file -DgroupIdcom.chinacreator.sm -DartifactIdfbm-sm-common -Dversion0.0.1 -Dpackagingjar -Dfile../newJar/fbm-sm…

【LeetCode热题100】--160.相交链表

160.相交链表 使用双指针&#xff1a; /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/ public class Solution {public ListNode getInter…

数字孪生在智慧城市应用场景中的五大特点

数字孪生城市提出至今&#xff0c;已从概念、框架走向落地深耕&#xff0c;逐渐演变成为城市变革新动力和城市转型新路径&#xff0c;是智慧城市发展演进的重要方向。 数字孪生城市建设现已加速步入“技术多维集成、场景创新重构、市场成效导向”的落地实施时期。这一时期&…

第三十九章 持久对象和SQL - 持久类的 SQL 映射

文章目录 第三十九章 持久对象和SQL - 持久类的 SQL 映射持久类的 SQL 映射对象 SQL 映射的演示 对象 SQL 映射的基础知识Classes and Extents 第三十九章 持久对象和SQL - 持久类的 SQL 映射 持久类的 SQL 映射 对于任何持久类&#xff0c;该类的每个实例都可以作为表中的一…

前端项目练习(练习-003-webpack-01)

学习webpack前&#xff0c;首先&#xff0c;创建一个web-003项目&#xff0c;内容和web-002一样。&#xff08;注意将package.json中的name改为web-003&#xff09; 想想&#xff0c;我们开发Java 的时候&#xff0c;Maven帮我们做的主要是编译&#xff0c;打包等等内容。开发前…

【EI会议征稿】第八届能源系统、电气与电力国际学术会议(ESEP 2023)

第八届能源系统、电气与电力国际学术会议&#xff08;ESEP 2023&#xff09; 2023 8th International Conference on Energy System, Electricity and Power 第八届能源系统、电气与电力国际学术会议&#xff08;ESEP 2023&#xff09;定于2023年11月24-26日在中国武汉隆重举…

【教程】视频汇聚/视频监控管理平台EasyCVR录像存储功能如何优化?具体步骤是什么?

视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同&#xff0c;支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。视频监控系统EasyCVR拓展性强&#xff0c;视频能力丰富&#xff0c;具体可实现视频监控直播、视频轮播、视频录像、云存储、…

丰田的国际化与转型困境:对中国车企的欧洲策略启示

摘要&#xff1a;欧洲市场的消费者汽车偏好多样,中国车企进军欧洲时,需考虑产品设计和当地法规。回顾历史,丰田汽车通过其独特管理理念,在美国从廉价品牌形象成功转型为高质量、受信赖的全球品牌。但进入电动汽车时代&#xff0c;日本车企因深度共生的传统供应链而转型坎坷。中…

EasyExcel的源码流程(导入Excel)

1. 入口 2. EasyExcel类继承了EasyExcelFactory类&#xff0c;EasyExcel自动拥有EasyExcelFactory父类的所有方法&#xff0c;如read()&#xff0c;readSheet()&#xff0c;write()&#xff0c;writerSheet()等等。 3. 进入.read()方法&#xff0c;需要传入三个参数(文件路径…

1024程序员节之天马低代码开发者大赛篇

卡奥斯第二届1024程序员节正在火热进行中&#xff01;本次活动由四个线上活动分会场线下会场组成&#xff0c;今天向大家详细介绍一下四大线上分会场中的“低代码分会场”~ 天马低代码开发者大赛于2023年9月22日至10月20日12: 00进行&#xff0c;活动设立能源和组态两个赛道&a…

算法竞赛备赛之动态规划训练提升,DP基础掌握

1.背包问题 1.1.01背包问题 01背包问题是在M件物品中选择若干件放在空间为W的背包中&#xff0c;每件物品的体积为W1&#xff0c;W2至Wn&#xff0c;价值为P1&#xff0c;P2至Pn&#xff0c;01背包的约束条件是给定几种物品&#xff0c;每种物品有且只有一个&#xff0c;并且…

深入理解Java单例模式和优化多线程任务处理

目录 饿汉模式懒汉模式单线程版多线程版双重检查锁定 阻塞队列 单例模式能保证某个类在程序中只存在唯一一份实例, 而不会创建出多个实例&#xff0c;并提供一个全局访问点。 饿汉模式 类加载的同时&#xff0c;创建实例。 class Singleton {private static final Singlet…