数据结构与算法 算法的时间复杂度是怎么求的_百度知道
数据结构与算法 算法的时间复杂度是怎么求的
因为，我是初学者，所以请大虾以最简单明了的形式给我讲解下哈
说得好我一定追加分数。
我有更好的答案
那么这个复杂度就是O(n)for(i=0;i&这里做的次数是n次就是求一个多项式;i&n;i++);j&n;j++);n;i++)for(j=i+1，比如for(i=0
能不能解释下像O(log2n)还有O（n0.5）这类的 到底是怎么知道的
log2n一般都写成log(n)这个是以2为底的比如while(n&0){
n/=2;}这个做的次数是对数级的复杂度是log(n)的，这种复杂是非常不错的O（n^0.5）是开方级的for(i=0;i*i&=n;i++);这个就是开方级别的
采纳率：47%
来自团队：
为您推荐：
其他类似问题
您可能关注的内容
数据结构与算法的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。while(s&n)
这个题不难
给你一个相似的例子，你照着来吧
一个特定相关信息的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：
T (n) = O(f(n))
称T (n) 为算法的渐近时间复杂度（Asymptotic Time Complexity）,简称时间复杂度。O是数量级的符号。
下面我们探讨一下如何估算算法的时间复杂度
算法 = 控制结构 + 原操作（固有数据类型的操作）
算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间
算法的执行时间与原操作执行次数之和成正比
我们先介绍一个概念：
fo(j=1;j=n;++j)
fo(k=1;k=n;++k){++x;x+=x;}
语句重复执行的次数被称为语句的频度（Fequency Count）上程序段中++x的语句频度就是n2。
我们经常采用：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作...
这个题不难
给你一个相似的例子，你照着来吧
一个特定相关信息的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：
T (n) = O(f(n))
称T (n) 为算法的渐近时间复杂度（Asymptotic Time Complexity）,简称时间复杂度。O是数量级的符号。
下面我们探讨一下如何估算算法的时间复杂度
算法 = 控制结构 + 原操作（固有数据类型的操作）
算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间
算法的执行时间与原操作执行次数之和成正比
我们先介绍一个概念：
fo(j=1;j=n;++j)
fo(k=1;k=n;++k){++x;x+=x;}
语句重复执行的次数被称为语句的频度（Fequency Count）上程序段中++x的语句频度就是n2。
我们经常采用：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作多数情况下是最深层次循环内的语句中的原操作。
fo (i=1; i=n; ++i)
fo (j=1; j=n; ++j) {
c[i,j] = 0;
fo (k=1; k=n; ++k)
c[i,j] += a[i,k]*[k,j];
}
该算法的基本操作是乘法操作。时间复杂度为 O(n3)
答: 应该是D吧 没错了
答: 我可以给你提供个想法，仅供参考咯~！
可以从培训人才和被培训人才的数据比例来说明拉，很有说服力哦~！
祝你好运！
答: 你可以看一下
答: 你好。其实这个你可以网购的,网上有很多现实中买不到的书,不知道你那里有木有图书大厦,去图书大厦看看
大家还关注
Copyright &
Corporation, All Rights Reserved
确定举报此问题
举报原因(必选)：
广告或垃圾信息
激进时政或意识形态话题
不雅词句或人身攻击
侵犯他人隐私
其它违法和不良信息
报告，这不是个问题
报告原因(必选)：
这不是个问题
这个问题分类似乎错了
这个不是我熟悉的地区在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。
标签：至少1个，最多5个
一：渐近符号
1.1 符号的辨析
1.1.1 符号$O$
$O$，读作“大O”，非正式来说，$O(g(n))$是增长次数小于等于$g(n)$及其常数倍（$n$趋向于无穷大）的函数集合。
定义 如果函数$f(n)$包含在$O(g(n))$中，记作$f(n)∈O(g(n))$（平时使用为了方便书写，我们通常使用$f(n)=O(g(n))$代替）。它的成立条件是：对于所有足够大的$n$，$f(n)$的上界由$g(n)$的常数倍所确定，也就是说，存在大于0的常数$c$和非负整数$n_0$，使得：
$$对于所有的n≥n_0来说，f(n)≤c(g(n)$$
下图说明了这个定义：
下面给出几个例子：
$$\begin{align}n&=O(n^2)\tag{1.1.1.1}\\100n+5&=O(n^2)\tag{1.1.1.2}\\\frac 12n(n-1)&=O(n^2)\tag{1.1.1.3}\\n^3&≠O(n^2)\tag{1.1.1.4}\\0.00001n^3&≠O(n^2)\tag{1.1.1.5}\end{align}$$
1.1.2 符号$Ω$
$Ω$，读作“omega”，$Ω(g(n))$是增长次数大于等于$g(n)$及其常数倍（$n$趋向于无穷大）的函数集合。
定义 如果函数$f(n)$包含在$Ω(g(n))$中，记作$f(n)=Ω(n))$。它的成立条件是：对于所有足够大的$n$，$f(n)$的下界由$g(n)$的常数倍所确定，也就是说，存在大于0的常数$c$和非负整数$n_0$，使得：
$$对于所有的n≥n_0来说，f(n)≥c(g(n)$$
下图说明了这个定义：
下面给出几个例子：
$$\begin{align}n^3&=Ω(n^2)\tag{1.1.2.1}\\\frac 12n(n-1)&=Ω(n^2)\tag{1.1.2.2}\\100n+5&≠Ω(n^2)\tag{1.1.2.3}\end{align}$$
1.1.3 符号$Θ$
读作“theta”。
定义 如果函数$f(n)$包含在$Θ(g(n))$中，记作$f(n)=Θ(n))$。它的成立条件是：对于所有足够大的$n$，$f(n)$的上界和下界由$g(n)$的常数倍所确定，也就是说，存在大于0的常数$c_1,c_2$和非负整数$n_0$，使得：
$$对于所有的n≥n_0来说，c_1g(n)≤f(n)≤c_2g(n)$$
下图说明了这个定义：
下面给出几个例子：
$$\begin{align}\frac 12n(n-1)&=Θ(n^2)\tag{$c_1=\frac 14,c_2=\frac 12,n_0=2$}\\6n^3&≠Θ(n^2)\tag{1.1.3.2}\end{align}$$
1.2 符号的性质
定理 如果$t_1(n)=O(g_1(n))$并且$t_2(n)=O(g_2(n))$，则
$$t_1(n)+t_2(n)=O(\max\{g_1(n),g_2(n)\})$$
对于$Ω$和$Θ$符号，同样成立。
证明 增长次数的证明是基于以下简单事实：对于$4$个任意实数$a_1,b_1,a_2,b_2$，如果$a_1≤b_1$并且$a_2≤b_2$，则$a_1+a_2≤2\max\{b_1,b_2\}$。
因为$t_1(n)=O(g_1(n))$，存在正常量$c_1$和非负整数$n_1$，使得：
$$对于所有的n≥n_1,t_1(n)≤c_1g_1(n)$$
同样，因为$t_2(n)=O(g_2(n))$，
$$对于所有的n≥n_2,t_2(n)≤c_2g_2(n)$$
假设$c_3=\max\{c_1,c_2\}$并且$n≥\max\{n_1,n_2\}$，就可以利用两个不等式的结论将其相加，得出以下结论：
$$\begin{align}t_1(n)+t_2(n)&≤c_1g_1(n)+c_2g_2(n)\tag{1.2.1}\\&≤c_3g_1(n)+c_3g_2(n)=c_3[g_1(n)+g_2(n)]\tag{1.2.2}\\&≤c_3?2\max\{g_1(n),g_2(n)\}\tag{1.2.3}\end{align}$$
那么，对于两个连续执行部分组成的算法，应该如何应用这个特性呢？它意味着该算法的整体效率是由具有较大增长次数的部分所决定的，即效率较差的部分决定。
二：复杂度求解方法分析
对于一个普通函数（即非递归函数），其时间复杂度自然易求。下面我们主要谈谈如何求解递归函数的时间复杂度。
递归函数通常会有以下的方程式：
$$T(n)=aT(\frac nb)+f(n)\tag{2.1}$$
其中，$a≥1,b&1$，且都是常数，$f(n)$是渐近正函数。递归式（2.1）描述的是这样一种算法的运行时间：它将规模为$n$的问题分解为$a$个子问题，每个子问题规模为$\frac nb$，其中$a≥1,b&1$。$a$个子问题递归地求解，每个花费时间$T(\frac nb)$。函数$f(n)$包含了问题分解和子问题解合并的代价。
常用的方法有两种：主定理和分治法。
2.1 主定理（Master Theorem）
定理 令$a≥1,b&1$，且都是常数，$f(n)$是一个函数，$T(n)$是定义在非负整数上的递归式，即：
$$T(n)=aT(\frac nb)+f(n)$$
其中我们将$\frac nb$解释为$?\frac nb?$或$?\frac nb?$。那么$T(n)$有如下渐近界：
（Case 1）如果$f(n)=O(n^c)$，其中$c&log_ba$，则：
$$T(n)=Θ(n^{log_ba})$$
（Case 2）如果存在常数$k≥0$，使$f(n)=Θ(n^clog^{k}n)$，其中$c=log_ba$，则：
$$T(n)=Θ(n^clog^{k+1}n)$$
（Case 3）如果$f(n)=Ω(n^c)$，其中$c&log_ba$，并且对某个常数$k&1$和所有足够大的$n$有$af(\frac nb)≤kf(n)$，则：
$$T(n)=Θ(f(n))$$
算法导论已有关于这个定理的证明，故此处省略，有兴趣的读者可以去翻阅下。
2.2 分治法
分治法先把给定的实例划分为若干个较小的实例，对每个实例递归求解，然后如果有必要，再把较小实例的解合并成给定实例的一个解。假设所有较小实例的规模都为$\frac nb$，其中$a$个实例需要实际求解，对于$n=b^k,k=1,2,3...$，其中$a≥1,b&1$，得到以下结果：
$$\begin{align}T(n)&=aT(\frac nb)+f(n)\tag{原始递归方程式}\\T(b^k)&=aT(b^{k-1})+f(b^k)\tag{2.2.2}\\&=a[aT(b^{k-2})+f(b^{k-1})]+f(b^k)=a^2T(b^{k-2})+af(b^{k-1})+f(b^k)\tag{2.2.3}\\&=a^3T(b^{k-3})+a^2f(b^{k-2})+af(b^{k-1})+f(b^k)\tag{2.2.4}\\&=...\tag{2.2.5}\\&=a^kT(1)+a^{k-1}f(b^1)+a^{k-2}f(b^2)+...+a^0f(b^k)\tag{2.2.6}\\&=a^k[T(1)+\sum_{j=1}^{k} {\frac {f(b^j)}{a^j}}]\tag{2.2.7}\end{align}$$
由于$a^k=a^{log_bn}=n^{log_ba}$,当$n=b^k$时，对于式（2.2.7）我们可以推出下式：
$$T(n)=n^{log_ba}[T(1)+\sum_{j=1}^{log_bn}{\frac {f(b^j)}{a^j}}]\tag{2.2.8}$$
显然，$T(n)$的增长次数取决于常数$a$和$b$的值以及函数$f(n)$的增长次数。
三：无意发现的定理
以下是我自己在演算时无意发现的，并给出了证明。该定理依旧建立在递归方程式中，即：
$$T(n)=aT(\frac nb)+f(n)\tag{$a≥1,b&1$}$$
根据以上的方程式有以下两个定理：
定理1 对于递归方程式，若$a=1,b&1,f(n)=c,c$为某个常数，即：
$$T(n)=T(\frac nb)+c$$
$$T(n)=Θ(logn)$$
证明 应用主定理 Case 2，其中$c=log_ba=log_b1=0$，再使$k=0$，则$f(n)=Θ(n^clog^kn)=Θ(1)$，这里的$f(n)$即等于常数$c$，证明成立。
定理2 对于递归方程式，若$a=1,b&1,f(n)=kn+p$，其中$k&0,p&0$且为某个常数（也就是$f(n)$是一个线性直线方程），即：
$$T(n)=T(\frac nb)+(kn+p)\tag{$b&1,k&0,p$为某个常数}$$
$$T(n)=Θ(n)$$
证明 应用分治法中式（2.2.8）：
$$\begin{align}T(n)&=n^{log_ba}[T(1)+\sum_{j=1}^{log_bn}{\frac {f(b^j)}{a^j}}]\tag{3.2.1}\\&=\sum_{j=1}^{log_bn}{(kb^j+p)}\tag{3.2.2}\\&=plog_bn+\frac {kb}{b-1}(n-1)\tag{$k&0,p&0,b&1$}\\&&pn+\frac {kb}{b-1}(n-1)\tag{3.2.4}\\&=cn-\frac {kb}{b-1}\tag{$c&0$且为某个常数}\\&=Θ(n)\tag{3.2.5}\end{align}$$
证明成立。
第一部分辨析了$O,Ω,Θ$三种符号的区别以及它们的性质。
第二部分介绍了两种常用的计算时间复杂度方法，即主定理和分治法。
第三部分给出了个人在演算时发现的两个定理，并给出了证明，题外话，这两条定理比较实用，希望读者能够熟记。另外如果您在其它网站看到类似原创定理，纯属巧合，勿喷。
参考文献：[1] Thomas H.Cormen,etc. 算法导论（第三版）.[2] Anany Levitin. 算法设计与分析基础（第三版）.[3] . . Wikipedia.
文章转自我的个人博客：
0 收藏&&|&&0
你可能感兴趣的文章
20 收藏，3.9k
7 收藏，411
4 收藏，319
分享到微博？
我要该，理由是：
在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。