初入算法(1)—— 进入算法世界

2022-11-20 09:49:04 浏览数 (1)

14天阅读挑战赛

加油ヾ(◍°∇°◍)ノ゙,每天进步一点点,每日成长一步步!


目录

前言介绍

 一.什么是算法

1.在书中所讲到

2.我个人认为

二.算法的复杂性

三,算法的五个特征:

四.“好”算法的标准如下

五.时间复杂性

1.什么是时间复杂性

2.渐近上界

 3.渐近下界

六.空间复杂性

1.什么是空间复杂性

2.算法占用的存储空间包括


前言介绍

在CSDN中偶然发现活动中有个14天阅读挑战赛,点进去一看发现是关于算法的一些东西,我作为一个对于算法是什么东西的人,我决定尝试进入一下这个未知的领域,接下来我将会在作者团队的带领下去学习算法,了解算法,逐渐走进算法的领域。

作者简介:一名在校计算机学生、每天分享学习经验、和学习笔记。   座右铭:低头赶路,敬事如仪  点赞,收藏,评论,支持一下博主~ 谢谢~~

 一.什么是算法

1.在书中所讲到

瑞士著名的科学家Niklaus Wirth教授曾提出:数据结构 算法=程序。 数据结构是程序的骨架,算法是程序的灵魂。 在生活中,算法无处不在。每天早上起来,刷牙、洗脸、吃早餐,都在算着时间,以免上班或上课迟到;去超市购物,在资金有限的情况下,考虑先买什么、后买什么,算算是否超额;在家中做饭,用什么食材、调料,具体的烹饪方法和步骤如何,做完了还要品尝一下咸淡,看看是否做熟。所以,不要说你不懂算法,其实你每天都在用!

2.我个人认为

算法就是通过一些指令,用系统的方法描述解决问题的策略机制。通俗讲就是用于计算的方法,通过该这种方法可以达到预期的结果。


二.算法的复杂性

1.相对于算法来说,他并不会特别的简单,他有复杂,有简单。

算法复杂性的度量主要是针对运行该算法所需要的计算机资源的多少。当算法所需要的资源越多,该算法的复杂性越高;反之,当算法所需要的资源越少,算法的复杂性越低。对于任意给定的一个问题,设计出复杂性尽可能低的算法是在设计算法时追求的重要目标之一;而当给定的问题存在多种算法时,选择其中复杂性最低的算法是选用算法时遵循的重要准则。因此,算法的复杂性分析对算法的设计或选用具有重要的指导意义和实用价值。

2.算法是对特定问题求解步骤的一种描述

算法只是对问题求解方法的一种描述,它不依赖于任何一种语言,既可以用自然语言、程序设计语言(C、C 、Java、Python等)描述,也可以用流程图、框图来表示。通常情况下,为了更清楚地说明算法的本质,我们会去除计算机语言的语法规则和细节,采用“伪代码”来描述算法。“伪代码”介于自然语言和程序设计语言之间,它更符合人们的表达方式,容易理解,但它不是严格的程序设计语言。如果要上机调试,则需要转换成标准的计算机程序设计语言才能运行。


三,算法的五个特征:

一个典型的算法一般都可以抽象出5个特征

有穷性:算法的指令或者步骤的执行次数和时间都是有限的。(有限的)

确切性:算法的指令或步骤都有明确的定义。(明确的)

输入:有相应的输入条件来刻画运算对象的初始情况。

输出:一个算应有明确的结果输出。

可行性:算法的执行步骤必须是可行的。(可执行性)


四.“好”算法的标准如下

  1.  正确性:正确性是指算法能够满足具体问题的需求,程序运行正常,无语法错误,能够通过典型的软件测试,达到预期。
  2. 易读性:算法遵循标识符命名规则,简洁易懂,注释语句恰当适量,方便自己和他人阅读,便于后期调试和修改。
  3. 健壮性:算法对非法数据及操作有较好的反应和处理。例如,在学生信息管理系统中登记学生年龄时,若将21岁误输入为210岁,则系统应该有错误提示。
  4. 高效性:高效性是指算法运行效率高,即算法运行所消耗的时间短。
  5. 低存储性:低存储性是指算法所需的存储空间小。对于像手机、平板电脑这样的嵌入式设备,算法如果占用空间过大,则无法运行。算法占用的空间大小被称为空间复杂度。

五.时间复杂性

1.什么是时间复杂性

简单来说就是算法运行需要时间

一般情况下,对于一个算法的复杂性分析主要是对算法效率的分析,包括衡量其运行速度的时间效率及衡量其运行时所需要占用空间大小的空间效率。

对于算法的时间效率的计算,通常是抛开与计算机硬件、软件有关的因素,仅考虑实现该算法的高级语言程序。一般而言,对程序执行的时间复杂度的分析是分块进行的,先分析程序中的语句,再分析各程序段,最后分析整个程序的执行复杂度。通常以渐进式的大O(希腊字母Omicron,奥米克戎)形式来表示算法的时间复杂度。渐进式的大O形式表示时间复杂度的主要运算规则有如下2种

例子:

2.渐近上界

T(n)和Cf(n)的函数曲线如图1-1所示。从图1-1可以看出,当n大于等于n0时,T(n)sCf(n);当n足够大时,T(n)和f(n)近似相等。因此,我们用O(f(n))表示时间复杂度渐近上界,可以用这种表示法衡量算法的时间复杂度。算法1-3的时间复杂度渐近上界为O(f(n))=O(n2),用极限可以表示为

3.渐近下界

渐近下界符号Ω(T(n)≥Cf(n)),如图1-2所示。从图1-2可以看出,当n大于等于n0时,T(n)大于等于Cf(n));当n足够大时,T(n)和f(n)近似相等。因此,我们用(Ω(f(n))来表示时间复杂度渐近下界。

在实际应用中,通常使用时间复杂度渐近上界O(f(n))来表示时间复杂度。

有些算法,如排序、查找、插入算法等,可以分为最好、最坏和平均情况分别求算法渐近复杂度。但考查一个算法时通常考查最坏的情况,而不是考查最好的情况,最坏情况对衡量算法的好坏具有实际意义。


六.空间复杂性

1.什么是空间复杂性

算法占用空间的大小

一般情况下,一个算法所占用的存储空间包括算法自身、算法的输入、算法的输出及实现算法的在程序运行时所占用空间的总和。

2.算法占用的存储空间包括

  1. 输入/输出数据
  2. 算法本身
  3. 额外需要的辅助空间

输入/输出数据占用的空间是必需的,算法本身占用的空间可以通过精简算法来缩减,但缩减的量是很小的,可以忽略不计。算法在运行时所使用的辅助变量占用的空间(即辅助空间)才是衡量算法空间复杂度的关键因素。


本篇文章就先讲解这些,我后续将会持续更新算法文章。


 创作不易,求关注,点赞,收藏,谢谢~

0 人点赞