算法 - 请问时间频度和时间复杂度是一个概念吗？

问题描述

问 题

一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。

一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数，用 T(n)表示，若有某个辅助函数 f(n),使得当 n 趋近于无穷大时，T （ n)/f(n)的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作 T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

这两段话来源于
http://www.cnblogs.com/yuzhuw...
http://www.cnblogs.com/dzhs/p...
等多个 blog

注: 通过搜索以后，给的答案普遍没有解释 T(n)这个记号的问题，另外，也有看到时间频度用 f(n)表示，所以更加困惑了

1.那么请问这两者是一个概念吗？如果不是，那么为什么都用 T(n)表示呢？

2.f(n)这个函数是否表示时间频度呢？或者是有其他实际含义？

谢谢大家帮忙解答

解决方案

时间频度是指算法中语句的执行次数, 用$T(n)$表达, $n$为问题规模.

不过实际中, 时间频度的表达方法有点复杂. 所以引出了时间复杂度的概念. 如果有辅助函数$f(n)$, 在n趋于无限大, 此时, $\frac{T(n)}{f(n)}$的极限值是不为零的常数, 则可以(近似的)用$f(n)$代替$T(n)$, 记为$T(n) = O(f(b))$, 也称算法的渐进复杂度.

另外, 我看到你在v2ex也提了这个问题, 里面回答的geelaw(姚班)大神其实开过一门算法导论, 就是文字加代码模式的. 人家不好意思自产自销, 所以我偷偷来帮他宣传下, 哈哈

这篇关于算法 - 请问时间频度和时间复杂度是一个概念吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！