哪种操作跟算法的具体实现无关？ 一条赋值语句同时包含了（表达式）计算和（变量）存储两个基本资源 前100000个整数求和对比前1000个整数求和，算是一个问题的更大规模 用动态的眼光看，就是当问题规模增大的时候，T(n)中的一些部分会盖过其他部分的贡献 称作”大O“表示法，记作O(f(n))，其中f(n)表示T(n)中的主导部分 当n增大时，常数1在最终结果中显得越来越无足轻重，所以可以去掉1，保留n作为主要部分，运行时间数量级就是O(n) 当n很小时，常数1005起决定性作用 分为最好、最差和平均情况，平均状况体现了算法的主流性能，对算法的分析要看主流，而不被某几种特定的运行状况所迷惑。 T(n) = 3 + 3n^2+2n+1=3*n^2+2n+4 表示了所有上限中最小的那个上限
算法时间度量指标
一个算法所实施的操作数量或步骤数可作为独立于具体程序/机器的度量指标
需要一种通用的基本操作来作为运行步骤的计量单位赋值语句是一个合适的选择
问题规模影响算法执行时间
问题规模：影响算法执行时间的主要因素
在前n个整数累计求和的算法中，需要累计的整数个数合适作为问题规模的指标
算法分析的目标是要找出问题规模会怎么影响一个算法的执行时间
数量级函数
基本操作数量函数 T(n)的精确值并不是特别重要，重要的是T(n)中起决定性因素的主导部分
数量级函数描述了T(n)中随着n增加而增加速度最快的主导部分
确定运行时间数量级大O的方法
例1：T(n)=1+n
例2：T(n)=5n^2+27n+1005
当n越来越大时，n^2越来越重要
同样n^2中的系数5，对于n^2的增长速度来说也影响不大
所以去掉27n+1005，以及系数5的部分，确定为O(n^2)影响算法运行时间的其他因素
有时决定运行时间的不仅是问题规模
某些具体数据也会影响算法运行时间
常见的大O数量级函数
通常当n较小时，难以确定其数量级
当n增长到较大时，容易看出其主要变化量级
f(n)
名称
1
常数
log(n)
对数
n
线性
n*log(n)
对数线性
n^2
平方
n^3
立方
2^n
指数
从代码分析确定执行时间数量级函数
a = 5 b = 6 c = 10 for i in range(n): for j in range(n): x = i * i y = j * j z = i * j for k in range(n): w = a * k + 45 v = b * b d = 33
仅保留最高阶项n^2，去掉所有系数，数量级为O(n^2)大O表示法
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
142