发布于2019-10-11 14:04 阅读(873) 评论(0) 点赞(27) 收藏(1)
程序设计 = 数据结构 + 算法
我们把数据结构分为逻辑结构和物理结构,逻辑结构是面向问题的,而物理结构就是面向计算机的,其基本目标是将数据及其逻辑关系存储到计算机的内存中。 逻辑结构:是指数据对象中数据元素之间的相互关系。 逻辑结构分为四种:
物理结构:是指数据的逻辑结构在计算机中的存储形式。 数据元素的存储结构形式有两种,分别是顺序存储和链接存储:
数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。 抽象:是指抽取出事物具有的普遍性的本质。 抽象数据类型(Abstract Data Type, ADT):是指一个数学模型及定义在该模型上的一组操作。一个抽象数据类型定义了:一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。至于,一个数据类型到底需要哪些操作,这就只能由设计者根据实际需要来定。
算法:算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
算法具有五个基本特性:
算法设计的要求:
算法的 正确 分为四个层次:
我们把层次 3 作为一个算法是否正确的标准。
函数的渐进增长:给定两个函数 f(n) 和 g(n),如果存在一个整数 N,使得对于所有的 n > N,f(n) 总是比 g(n) 大,那么,我们说 f(n) 的增长渐进快于 g(n)。 通过分析函数的渐进增长,我们有如下推论:
在进行算法分析时,语句总的执行次数 T(n) 是关于问题规模 n 的函数,进而分析 T(n) 随 n 变化情况并确定 T(n) 的数量级。算法的时间复杂度,也就是算法的时间度量,记作:T(n) = O(f(n))。它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中 f(n) 是问题规模 n 的某个函数。 这样用大写 O()来体现算法时间复杂度的记法,我们称之为大O记法。随着 n 的增大,T(n) 增长最慢的算法为最优算法。
得到的结果就是大 O 阶。 常见的时间复杂度:
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
复制代码
除非特别指定,我们提到的运行时间都是最坏情况的运行时间。
算法的空间复杂度是通过计算算法所需的存储空间实现,记作:S(n) = O(f(n))
,其中,n 为问题的规模,f(n) 为语句关于 n 所占存储空间的函数。
若算法执行时间所需要的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为 O(1)。
对于算法的复杂度,一般是指时间复杂度。
作者:343489399
链接:https://www.pythonheidong.com/blog/article/134269/a048b791c8e98efd4cf8/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!