『算法导论』什么是算法？什么是程序？_什么是算法程序-程序员宅基地

技术标签：算法数据结构

活动地址：CSDN21天学习挑战赛

作者简介：一位喜欢写作，计科专业大二菜鸟

个人主页：starry陆离

首发日期：2022年8月2日星期二

上期文章：『首期文章』

订阅专栏：『算法分析与设计』
如果文章有帮到你的话记得点赞+收藏支持一下哦

在这里插入图片描述

『算法导论』什么是算法？什么是程序？

1.什么是算法
2.“算法”的来源
3.什么是程序
4.三种常用的描述算法的形式
5.算法的好与坏
6.算法复杂性的渐近性态
7.时间复杂性渐进表示法
8.常见的算法复杂度的大O阶

1.什么是算法

算法(Algorithm)是指解决问题的方法或过程，它包含一系列步骤，用来将输入数据转换成输出结果

算法具有以下性质：

输入：有零个或多个输入
输出：至少有一个输出
确定性：组成算法的每条指令清晰、无歧义
有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限

2.“算法”的来源

算法(Algorithm) 一词来源于著名的波斯帝国塔吉克族数学家、天文学家、地理学家—— 阿尔·花剌子模(Al-Khwarizmi)，其拉丁名为阿尔戈利兹姆(Algorismus)

他是代数与算术的创立人，被誉为**“代数之父”**。“代数(Algebra)”源于他的一本书的标题，而“算法(Algorism、Algorithm)”源于他的拉丁文名

3.什么是程序

程序(Program)是算法用某种程序设计语言的具体实现

程序不一定满足有限性

这一点是算法和程序的最大区别，算法是有限的，但是程序是可能无限的；例如操作系统只要不关机就是一个无限期执行的程序

4.三种常用的描述算法的形式

自然语言

优点：通俗易懂
缺点：但缺乏直观性和简洁性，且易产生歧义。
举例： “南京市长江大桥”、“这个人连我都不认识”、“我曾经喜欢一个人，我现在喜欢一个人”……

程序流程图

优点：描述算法形象、直观，容易理解，
绘制过程比较费时费力，难以修改。

伪代码

优点：简单易懂，修改容易，易于转化为程序语言代码
缺点：伪代码格式难以规范

5.算法的好与坏

一个算法的好与坏一般是用时间复杂度和空间复杂度来衡量。

算法复杂性 = 算法所需要的计算机资源，用N、I 来表示算法要解决问题的规模和算法的输入，用C表示算法的复杂性，有：C =F(N,I)

算法的时间复杂性T(n)：如果问题的规模为n，在算法输入为I时算法所需的时间资源为T(N,I) ，T(N,I)称为算法的时间复杂性

算法的空间复杂性S(n)：如果问题的规模为n，在算法输入为I时算法所需的空间资源为S(N,I) ，S(N,I)称为算法的空间复杂性

6.算法复杂性的渐近性态

算法复杂性的渐近性态：对于F(N)，如果存在F’(N)，使得当N→∞时有： (F(N )-F’(N )) / F(N ) → 0 则F’(N)是F(N)当N→∞时的渐近性态

例：F(N)=3N2+4Nlog2N +7，求F’(N)

F’(N)的一个答案是3N2，

7.时间复杂性渐进表示法

设f(N)和g(N)是定义在正数集上的正函数。

O的定义：如果存在正的常数C和自然数N0，使得当N >= N0时有f(N) <= Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为 f(N)=O(g(N))，即f(N)的阶不高于g(N)的阶

例：

对所有N >=1时，3N <=4N，故3N=O(N)
对所有N>=1时，N+1024 <=1025N，故N+1024=O(N)
对所有N >=10时，2N²+11N-10 <=3N²，故2N²+11N-10=O(N² )
对所有N >=1时，N² <=N³，故N²=O(N³ )

练习题：对于f(n)=n，下列说法错误的是（显然选B）

A. f(n)=O(n) • B. f(n)=O(1/n) • C. f(n)=O(n² ) • D. f(n)=O(n³ )

Ω的定义：如果存在正的常数C和自然数N0，使得当N >= N0时有f(N) >= Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为 f(N)=Ω(g(N))，即f(N)的阶不低于g(N)的阶。

例：

1024n+1024 = Ω(n)
n2+n+1 = Ω(n)
2n³+nlogn+1 = Ω(n² )

练习题：求下列函数的渐进表达式，用大O表示

• (1) 5n² + 10n =O(n²)

• (2) n + nlogn²=O(nlogn)

• (3) n² /100 + 3n =(O(n²))

• (4) 20 log3ⁿ =O(n)

• (5) 1/n² + 1 = O(1)

• (6) logn⁵ + n^1/2 = O(logn)

8.常见的算法复杂度的大O阶

O(1): 表示算法的运行时间为常量时间

O(logn): 二分查找等算法

O(n): 线性算法，例如线性查找

O(nlogn): 快速排序、归并排序等算法

O(n2 ): 对数组进行排序的简单算法，例如冒泡排序等

O(n3 ): 做两个n阶矩阵的乘法运算

O(2ⁿ ): 求具有n个元素集合的所有子集的算法

O(n!): 求具有n个元素的全排列的算法

本文链接：https://blog.csdn.net/weixin_53463734/article/details/126102763

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

FTP命令字和返回码_ftp 登录返回230-程序员宅基地

文章浏览阅读3.5k次，点赞2次，收藏13次。为了从FTP服务器下载文件，需要要实现一个简单的FTP客户端。FTP（文件传输协议）是 TCP/IP 协议组中的应用层协议。FTP协议使用字符串格式命令字，每条命令都是一行字符串，以“\r\n”结尾。客户端发送格式是：命令+空格+参数+"\r\n"的格式服务器返回格式是以：状态码+空格+提示字符串+"\r\n"的格式，代码只要解析状态码就可以了。读写文件需要登陆服务器，特殊用..._ftp 登录返回230

centos7安装rabbitmq3.6.5_centos7 安装rabbitmq3.6.5-程序员宅基地

文章浏览阅读648次。前提：systemctl stop firewalld 关闭防火墙关闭selinux查看getenforce临时关闭setenforce 0永久关闭sed-i'/SELINUX/s/enforcing/disabled/'/etc/selinux/configselinux的三种模式enforcing：强制模式，SELinux 运作中，且已经正确的开始限制..._centos7 安装rabbitmq3.6.5

idea导入android工程,idea怎样导入Android studio 项目？-程序员宅基地

文章浏览阅读5.8k次。满意答案s55f2avsx2017.09.05采纳率：46%等级：12已帮助：5646人新版Android Studio/IntelliJ IDEA可以直接导入eclipse项目,不再推荐使用eclipse导出gradle的方式2启动Android Studio/IntelliJ IDEA，选择 import project3选择eclipse 项目4选择 create project f..._android studio 项目导入idea 看不懂安卓项目

浅谈AI大模型技术：概念、发展和应用_ai大模型应用开发-程序员宅基地

文章浏览阅读860次，点赞2次，收藏6次。AI大模型技术已经在自然语言处理、计算机视觉、多模态交互等领域取得了显著的进展和成果，同时也引发了一系列新的挑战和问题，如数据质量、计算效率、知识可解释性、安全可靠性等。城市运维涉及到多个方面，如交通管理、环境监测、公共安全、社会治理等，它们需要处理和分析大量的多模态数据，如图像、视频、语音、文本等，并根据不同的场景和需求，提供合适的决策和响应。知识搜索有多种形式，如语义搜索、对话搜索、图像搜索、视频搜索等，它们可以根据用户的输入和意图，从海量的数据源中检索出最相关的信息，并以友好的方式呈现给用户。_ai大模型应用开发

非常详细的阻抗测试基础知识_阻抗实部和虚部-程序员宅基地

文章浏览阅读8.2k次，点赞12次，收藏121次。为什么要测量阻抗呢？阻抗能代表什么？阻抗测量的注意事项... ...很多人可能会带着一系列的问题来阅读本文。不管是数字电路工程师还是射频工程师，都在关注各类器件的阻抗，本文非常值得一读。全文13000多字，认真读完大概需要2小时。一、阻抗测试基本概念阻抗定义：阻抗是元器件或电路对周期的交流信号的总的反作用。AC 交流测试信号 (幅度和频率)。包括实部和虚部。图1 阻抗的定义阻抗是评测电路、元件以及制作元件材料的重要参数。那么什么是阻抗呢？让我们先来看一下阻抗的定义。首先阻抗是一个矢量。通常，阻抗是_阻抗实部和虚部

小学生python游戏编程arcade----基本知识1_arcade语言 like-程序员宅基地

文章浏览阅读955次。前面章节分享试用了pyzero,pygame但随着想增加更丰富的游戏内容，好多还要进行自己编写类，从今天开始解绍一个新的python游戏库arcade模块。通过此次的《连连看》游戏实现，让我对swing的相关知识有了进一步的了解，对java这门语言也有了比以前更深刻的认识。java的一些基本语法，比如数据类型、运算符、程序流程控制和数组等，理解更加透彻。java最核心的核心就是面向对象思想，对于这一个概念，终于悟到了一些。_arcade语言 like

随便推点

【增强版短视频去水印源码】去水印微信小程序+去水印软件源码_去水印机要增强版-程序员宅基地

文章浏览阅读1.1k次。源码简介与安装说明：2021增强版短视频去水印源码去水印微信小程序源码网站去水印软件源码安装环境（需要材料）：备案域名–服务器安装宝塔-安装 Nginx 或者 Apachephp5.6 以上-安装 sg11 插件小程序已自带解析接口，支持全网主流短视频平台，搭建好了就能用注：接口是公益的，那么多人用解析慢是肯定的，前段和后端源码已经打包，上传服务器之后在配置文件修改数据库密码。然后输入自己的域名，进入后台，创建小程序，输入自己的小程序配置即可安装说明：上传源码，修改data/_去水印机要增强版