溜冰后做爰在线网站,著名logo设计欣赏,免费网站建设品牌好,wordpress改变邮箱基本概念和术语 数据数据是信息的载体#xff0c;是描述客观事物属性的数#xff0c;字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。 数据元素数据元素是数据的基本单位#xff0c;通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成… 基本概念和术语 数据 数据是信息的载体是描述客观事物属性的数字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。 数据元素 数据元素是数据的基本单位通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成数据项是构成数据元素的不可分割的最小单位。例如学生记录就是一个数据元素它由学号、姓名、性别等数据项组成。 数据对象 数据对象是具有相同性质的数据元素的集合是数据的一个子集。例如整数数据对象是集合 \(N \lbrace 0, \pm 1, \pm 2, \cdots \rbrace\) 数据类型 数据类型是一个值的集合和定义在此集合上一组操作的总称。 1原子类型其值不可再分的数据类型。 2结构类型其值可以再分解为若干成分的数据类型。 3抽象数据类型抽象数据组织和与之相关的操作。 抽象数据类型 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性而与其在计算机内部如何表示和实现无关即不论其内部结构如何变化只要它的数学特性不变都有不影响其外部的使用。通常用数据对象、数据关系、基本操作集这样的三元组来表示抽象数据类型。 数据结构 在任何问题中数据元素都不是孤立存在的而是在它们之间存在着某种关系这种数据元素相互之间的关系称为结构。数据结构是相互之间存在的一种或多种特定关系的数据元素集合。数据结构包括三方面的内容逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构时密不可分的两个方面一个算法的设计取决于所选定的逻辑结构而算法的实现依赖于所采用的存储结构。 数据的逻辑结构 逻辑结构是指数据元素之间的逻辑关系即从逻辑关系上描述数据。它与数据的存储无关是独立于计算机的。 划分方法一 1线性结构 有且仅有一个开始和一个终端结点并且所有结点都最多只有一个直接前趋和一个后继。 例如线性表、栈、队列、串 2非线性结构 一个结点可能有多个直接前趋和直接后继。 例如树、图 划分方法二 集合 数据元素间除“同属于一个集合”外无其它关系 线性结构 一个对一个如线性表、栈、队列 树形结构 一个对多个如树 图形结构 多个对多个如图 数据的存储结构 存储结构是指数据结构在计算机中的表示又称映像也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言。数据的存储结构主要有顺序存储、链式存储、索引存储和散列存储。 1顺序存储把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里元素之间的关系有存储单元的邻接关系来体现。其优点是可以实现随机存取每个元素占用最少的存储空间缺点是只能使用相邻的一整块存储单元因此可能产生较多的外部碎片。2链接存储不要求逻辑上相邻的元素在物理位置上也相邻借助指示元素存储地址的指针表示元素之间的逻辑关系。其优点是不会出现碎片现象充分利用所有存储单元缺点是每个元素因存储指针而占用额外的存储空间并且只能实现顺序存储。3索引存储在存储元素信息的同时还建立附加的索引表。索引表中的每一项称为索引项索引项的一般形式是关键字地址。其优点是检索速度快缺点是增加了附加的索引表会占用较多的存储空间。另外在增加和删除数据时要修改索引表因而会花费较多额时间。4散列结构根据元素的关键字直接计算出该元素的存储地址又称为 Hash 存储。其优点是检索、增加和删除结点的操作都很快缺点是如果散列函数不好可能出现元素存储单元的冲突而解决冲突会增加时间和空间开销。注 数据的逻辑结构是以面向实际问题的角度出发的只采用抽象表达方式独立于存储结构数据的存储方式有多种不同的选择而数据的存储结构是逻辑结构在计算机上的映射它不能独立于逻辑结构而存在。数据结构包括三要素缺一不可。 算法的特性 算法是对特定问题求解步骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作。此外一个算法还具有下列 5 个重要特性。 1有穷性: 一个算法必须总是对任何合法的输入值在执行有穷步之后结束且每一步都可在有穷时间内完成。 2确定性: 算法中每一条指令必须有确切的含义读者理解时不会产生二义性。即对于相对的输入只能得出相同的输出。 3可行性: 一个算法是可行的即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 4输入 : 一个算法有零个或者多个的输入这些输入取自于每个特定的对象的集合。 5输出 : 一个算法有一个或者多个输出这些输出是同输入有着某种特定关系的量。 通常设计一个“好”的算法应考虑达到以下目标。 1正确性算法应当能够正确地解决求解问题。 2可读性算法应当具有良好的可读性以助于人民理解。 3健壮性当输入非法数据时算法也能适当地做出反应或进行处理而不会产生莫名其妙的输出结果。 4效率与低存储量需求效率是指算法执行的时间存储量需求是指算法执行过程中所需要的最大存储空间 这两者都与问题的规模有关。 算法效率的度量 算法效率的度量是通过时间复杂度和空间复杂度来描述的。 1、时间复杂度 一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记作 \(T(n)\)它是该算法问题规模 n 的函数时间复杂度主要分析 \(T(n)\) 的数量级。算法中的基本运算的频度与\(T(n)\)同数量级所以通常采用算法中基本运算的频度 \(f(n)\) 来分析算法的时间复杂度。因此算法的时间复杂度记为\(T(n)O(f(n))\) 上式中 O 的含义是 \(T(n)\) 的数量级其严格的数学定义是若 \(T(n)\) 和 \(f(n)\) 是定义在正整数集合上的两个函数则存在正常数 \(C\) 和 \(n_0\) 使得\(nn_0\)时都满足 \(\color{red}{0T(n)C*f(n)}\) 。其中 \(f(n)\) 是 \(T(n)\) 的一个渐近函数。 算法的时间复杂度不仅依赖于问题的规模 n也取决于待输入数据的性质。 例如 在数组 \(A[0, \cdots, n-1]\) 中查找定值 k 的算法大致如下 i n - 1;
while(i0 (A[i] ! k))i--;
return i; 此算法中的语句3基本运算的频度不仅与问题规模有关还与输入实例中 A 的各元素取值及 k 的取值有关 1若 A 中没有与 k 相等的元素则语句3的频度\(f(n) n\)。 2若 A 中的最有一个元素等于 k则语句3的频度\(f(n)\) 是常数 0。 最坏时间复杂度是指在最坏情况下算法的时间复杂度。 平均时间复杂度是指所有可能输入实例在等概率出现的情况下算法的期望运行时间。 最好时间复杂度是指在最好情况下算法的时间复杂度。 一般总是考虑在最坏情况下的时间复杂度以保证算法的运行时间不会比它更长。 在分析一个程序的时间复杂性时有以下两条规则 加法规则\(T(n)T1(n)T2(n)O(f(n))O(g(x))O(max(f(n),g(n)))\) 乘法规则\(T(n)T1(n) \times T2(n)O(f(n)) \times O(g(x))O(f(n) \times g(n))\) 常见的渐近时间复杂度 常量复杂度 \(O(1)\)对数复杂度 \(O(logn)\)线性复杂度 \(O(n)\)平方复杂度 \(O(n^2)\)指数复杂度 \(O(2^n)\)基本的复杂度如上基于以上的表达式可以有很多的组合其中 \(logn\) 默认情况下等同于 \(log_{2}n\) 大小关系 \(O(1) O(log_2n) O(n) O(nlog_2n) O(n^2) O(n^3) O(2^n) O(n!) O(n^n)\) 2、空间复杂度 算法的空间复杂度\(Sn\)定义为该算法所耗费的存储空间它是问题的规模\(n\)的函数。渐进空间复杂度简称为空间复杂度记作\(SnOgn\)。 一个上机程序除了需要存储空间来存放本身所用指令、常数、变量和输入数据外也需要一些对数据进行操作的工作单位和存储一些为实现计算所需信息的辅助空间若输入数据所占空间只取决于问题本身和算法无关组只需分析输入和程序之外的额外空间了。 算法原地工作是指算法所需辅助空间是常量即\(O1\)。 算法复杂的意义 算法复杂度的分级相当于高等数学的无穷大的阶反映了在规模\(n\)趋于无穷大的过程中算法代价增长的速度。算法的复杂度越高其实施的代价随着规模增大而增长的速度越快。 \(example\) \(斐波那契数列的第n项\) 递归算法def fib(n):if n 2:return 1else:return fib(n-1) fib(n-2) 将参数\(n\)看问题实例的规模不难看出计算\(F_n\)的时间代价考虑求加法操作的次数大致等于计算\(F_{n-1}\)和\(F_{n-2}\) 的时间代价之和。这一情况说明计算\(F_n\)的时间代价大致等比于斐波那契数\(F_n\)的值。根据已有的结论 \[ \mathop {\lim }\limits_{n \to \infty } {F_n} {(\frac{{\sqrt 5 1}}{2})^n}1.618^n \] 可以看到计算\(F_n\)的时间代价按\(n\)值的指数增长。 递推算法def fib(n):f1 f2 1for k in range(1,n):f1, f2 f2, f2 f1return f2 用这个算法计算\(F_n\)的值循环的工作只做一次循环需要做\(n-1\)次。每次循环中只执行了几个简单动作总的工作量基本操作执行次数与\(n\)值呈现某种线性关系。 这个例子说明解决同一问题的不同算法其计算复杂度的差异很大甚至具有截然不同的性质。通过分析算法复杂度可以帮助使用者选择适用的算法也可能发现已知算法的缺陷促使人们设法开发更好的算法 。 Python 内置类型性能分析 timeit 模块 timeit 模块可以用来测试一小段 Python 代码的执行速度。 class timeit.Timer(stmtpass, setuppass, timertimer function) Timer 是测量小段代码执行速度的类。 stmt 参数是要测试的代码语句statment setup 参数是运行代码时需要的设置 timer 参数是一个定时器函数与平台有关。 timeit.Timer.timeit(number1000000) Timer 类中测试语句执行速度的对象方法。number 参数是测试代码时的测试次数默认为 1000000 次。方法返回执行代码的平均耗时一个 float 类型的秒数。 list 的操作测试 def test1():l []for i in range(1000):l l [i]
def test2():l []for i in range(1000):l.append(i)
def test3():l [i for i in range(1000)]
def test4():l list(range(1000))from timeit import Timert1 Timer(test1(), from __main__ import test1)
print(concat ,t1.timeit(number1000), seconds)
t2 Timer(test2(), from __main__ import test2)
print(append ,t2.timeit(number1000), seconds)
t3 Timer(test3(), from __main__ import test3)
print(comprehension ,t3.timeit(number1000), seconds)
t4 Timer(test4(), from __main__ import test4)
print(list range ,t4.timeit(number1000), seconds)# (concat , 1.7890608310699463, seconds)
# (append , 0.13796091079711914, seconds)
# (comprehension , 0.05671119689941406, seconds)
# (list range , 0.014147043228149414, seconds) pop 操作测试 x range(2000000)
pop_zero Timer(x.pop(0),from __main__ import x)pop_zero Timer(x.pop(0),from __main__ import x)pop_zero Timer(x.pop(0),from __main__ import x)pop_zero Timer(x.pop(0),from __main__ import x)pop_zero Timer(x.pop(0),from __main__ import x)
print(pop_zero ,pop_zero.timeit(number1000), seconds)
x range(2000000)
pop_end Timer(x.pop(),from __main__ import x)
print(pop_end ,pop_end.timeit(number1000), seconds)# (pop_zero , 1.9101738929748535, seconds)
# (pop_end , 0.00023603439331054688, seconds) 测试 pop 操作从结果可以看出pop 最后一个元素的效率远远高于 pop 第一个元素 list 内置操作的时间复杂度 \[ \begin{array}{lc} Op O \ Efficiency \\ indexx[\ ] O(1) \\ index \ assignment O(1) \\ append O(1) \\ pop() O(1) \\ pop(i) O(n) \\ insert(i, item) O(n) \\ del \ operator O(n) \\ iteration O(n) \\ contain(in) O(n) \\ get \ slice[x:y] O(k) \\ del \ slice O(n) \\ set \ slice O(nk) \\ reverse O(n) \\ concatenate O(k) \\ sort O(nlogn) \\ multiply O(nk) \\ \end{array} \] 从上可以看出 list 大概是顺序表实现。 dict 内置操作的时间复杂度 \[ \begin{array}{lc} Op O \ Efficiency \\ copy O(1) \\ get \ item O(1) \\ set \ item O(1) \\ del \ item O(1) \\ contains(in) O(1) \\ iteration O(n) \\ \end{array} \] 转载于:https://www.cnblogs.com/oneTOinf/p/11453191.html
