blocks|key|598680|text|假设自然对数(否则只是乘以一个常数)，我们就有|type|unstyled|depth|inlineStyleRanges|entityRanges|data|598681|lim+{n->inf}+log+n+/+sqrt(n)+=+(inf+/+inf)|offset|length|style|CODE|598682|++++++++++++++++++++++++=++lim+{n->inf}+1/n+/+1/(2*sqrt(n))+(by+L'Hospital)
++++++++++++++++++++++++=++lim+{n->inf}+2*sqrt(n)/n
++++++++++++++++++++++++=++lim+{n->inf}+2/sqrt(n)
++++++++++++++++++++++++=++0+<+inf|code-block|syntax|javascript|598683|参考符号表示法对O(.)的替代定义，因此从上面我们可以说log+n+=+O(sqrt(n))，|598684|另外，比较下面函数的增长，对于所有的log+n，log+n总是以sqrt(n)为上限。|598685|​|598686|📷|atomic|598687|598688|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Big_O_notation|1|IMAGE|IMMUTABLE|imageUrl|https://developer.qcloudimg.com/http-save/yehe-900000/fdbd6d366e150fefb6d9216b907cf693.png|imageAlt^0|0|0|16|0|0|8|4|S|I|2|5|0|0|I|5|O|5|W|7|0|0|0|1|1|0|0^^$0|@$1|2|3|4|5|6|7|1A|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1B|8|@$D|1C|E|1D|F|G]]|9|@]|A|$]]|$1|H|3|I|5|J|7|1E|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|1F|8|@$D|1G|E|1H|F|G]|$D|1I|E|1J|F|G]]|9|@$D|1K|E|1L|1|1M]]|A|$]]|$1|O|3|P|5|6|7|1N|8|@$D|1O|E|1P|F|G]|$D|1Q|E|1R|F|G]|$D|1S|E|1T|F|G]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1U|8|@]|9|@]|A|$]]|$1|S|3|T|5|U|7|1V|8|@]|9|@$D|1W|E|1X|1|1Y]]|A|$]]|$1|V|3|R|5|6|7|1Z|8|@]|9|@]|A|$]]|$1|W|3|-4|5|6|7|20|8|@]|9|@]|A|$]]]|X|$Y|$5|Z|10|11|A|$12|13]]|14|$5|15|10|16|A|$17|18|19|-4]]]]

Assuming natural logarithms (otherwise just multiply by a constant), we have
<code>lim {n-&gt;inf} log n / sqrt(n) = (inf / inf)</code>
<pre><code> = lim {n-&gt;inf} 1/n / 1/(2*sqrt(n)) (by L'Hospital)
 = lim {n-&gt;inf} 2*sqrt(n)/n
 = lim {n-&gt;inf} 2/sqrt(n)
 = 0 &lt; inf
</code></pre>
Refer to <a href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noreferrer">https://en.wikipedia.org/wiki/Big_O_notation</a> for alternative defination of <code>O(.)</code> and thereby from above we can say <code>log n = O(sqrt(n))</code>,
Also compare the growth of the functions below, <code>log n</code> is always upper bounded by <code>sqrt(n)</code> for all <code>n &gt; 0</code>.
<a href="https://i.stack.imgur.com/0oZZQ.png" rel="noreferrer"><img src="https://i.stack.imgur.com/0oZZQ.png" alt="enter image description here" /></a>

blocks|key|602466|text|只需比较这两种功能：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|602467|sqrt(n)+----------+log(n)
n%5E(1/2)+----------+log(n)

Plug+in+Log
log(+n%5E(1/2)+)+---+log(+log(n)+)
(1/2)+log(n)+-----+log(+log(n)+)|code-block|syntax|javascript|602468|很明显：const+.log(n)+>+log(log(n))|offset|length|style|BOLD|602469|entityMap^0|0|0|4|R|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@$I|R|J|S|K|L]]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

Just compare the two functions:

<pre><code>sqrt(n) ---------- log(n)
n^(1/2) ---------- log(n)

Plug in Log
log( n^(1/2) ) --- log( log(n) )
(1/2) log(n) ----- log( log(n) )
</code></pre>

It is clear that: const . log(n) > log(log(n))

blocks|key|1872738|text|不，不是等价物。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1872739|@trincot在他的回答中给出了一个很好的解释和例子。我要再加一点。你的教授教你|1872740|any+operation+that+halves+the+length+of+the+input+has+an+O(log(n))+complexity|code-block|syntax|javascript|1872741|也是真的，|1872742|any+operation+that+reduces+the+length+of+the+input+by+2/3rd,+has+a+O(log3(n))+complexity
any+operation+that+reduces+the+length+of+the+input+by+3/4th,+has+a+O(log4(n))+complexity
any+operation+that+reduces+the+length+of+the+input+by+4/5th,+has+a+O(log5(n))+complexity
So+on+...|1872743|即使是(B-1)/Bth.对输入长度的所有缩减，它的复杂性都是O(logB(n))|offset|length|style|CODE|1872744|N:B:+O(logB(n))是指基于B的n对数。|1872745|entityMap^0|0|0|0|0|0|3|A|V|A|0|0|4|5|A|J|1|L|1|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|Z|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|10|8|@]|9|@]|A|$G|H]]|$1|M|3|N|5|6|7|11|8|@$O|12|P|13|Q|R]|$O|14|P|15|Q|R]]|9|@]|A|$]]|$1|S|3|T|5|6|7|16|8|@$O|17|P|18|Q|R]|$O|19|P|1A|Q|R]|$O|1B|P|1C|Q|R]|$O|1D|P|1E|Q|R]]|9|@]|A|$]]|$1|U|3|-4|5|6|7|1F|8|@]|9|@]|A|$]]]|V|$]]

No, It's not equivalent.

@trincot gave one excellent explanation with example in his answer. I'm adding one more point. Your professor taught you that 

<pre><code>any operation that halves the length of the input has an O(log(n)) complexity
</code></pre>

It's also true that, 

<pre><code>any operation that reduces the length of the input by 2/3rd, has a O(log3(n)) complexity
any operation that reduces the length of the input by 3/4th, has a O(log4(n)) complexity
any operation that reduces the length of the input by 4/5th, has a O(log5(n)) complexity
So on ...
</code></pre>

It's even true for all reduction of lengths of the input by <code>(B-1)/Bth.</code> It then has a complexity of <code>O(logB(n))</code>

<code>N:B:</code> <code>O(logB(n))</code> means <code>B</code> based logarithm of <code>n</code>

blocks|key|1677075|text|解决这个问题的一种方法是比较O的增长率(|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1677076|📷|atomic|offset|length|1677077|)|1677078|和O(|1677079|1677080|1677081|​|ordered-list-item|1677082|1677083|1677084|1677085|随着n的增加，我们看到(2)小于(1)。当n+=+10,000+eq-1等于0.005而eq-2等于0.0001时|style|BOLD|1677086|因此|1677087|1677088|越多越好。|1677089|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://developer.qcloudimg.com/http-save/yehe-900000/26290e849cf151d7293a2b781139f6c6.png|imageAlt|1|https://developer.qcloudimg.com/http-save/yehe-900000/85659a32dc30ab50fd77d31d7f554aac.png|2|https://developer.qcloudimg.com/http-save/yehe-900000/b361d07de553fdcc4c33438f7e3d693f.png|3|https://developer.qcloudimg.com/http-save/yehe-900000/d88889f14606d24e8d5c417ee8d0a0f8.png|4|https://developer.qcloudimg.com/http-save/yehe-900000/25c43e814b7c27a1b538d673e965ad90.png^0|0|0|1|0|0|0|0|0|1|1|0|0|0|0|1|2|0|0|0|1|3|0|L|A|12|5|1E|6|0|0|0|1|4|0|0^^$0|@$1|2|3|4|5|6|7|1I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|1J|8|@]|9|@$E|1K|F|1L|1|1M]]|A|$]]|$1|G|3|H|5|6|7|1N|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|1O|8|@]|9|@]|A|$]]|$1|K|3|C|5|D|7|1P|8|@]|9|@$E|1Q|F|1R|1|1S]]|A|$]]|$1|L|3|H|5|6|7|1T|8|@]|9|@]|A|$]]|$1|M|3|N|5|O|7|1U|8|@]|9|@]|A|$]]|$1|P|3|C|5|D|7|1V|8|@]|9|@$E|1W|F|1X|1|1Y]]|A|$]]|$1|Q|3|N|5|O|7|1Z|8|@]|9|@]|A|$]]|$1|R|3|C|5|D|7|20|8|@]|9|@$E|21|F|22|1|23]]|A|$]]|$1|S|3|T|5|6|7|24|8|@$E|25|F|26|U|V]|$E|27|F|28|U|V]|$E|29|F|2A|U|V]]|9|@]|A|$]]|$1|W|3|X|5|6|7|2B|8|@]|9|@]|A|$]]|$1|Y|3|C|5|D|7|2C|8|@]|9|@$E|2D|F|2E|1|2F]]|A|$]]|$1|Z|3|10|5|6|7|2G|8|@]|9|@]|A|$]]|$1|11|3|-4|5|6|7|2H|8|@]|9|@]|A|$]]]|12|$13|$5|14|15|16|A|$17|18|19|-4]]|1A|$5|14|15|16|A|$17|1B|19|-4]]|1C|$5|14|15|16|A|$17|1D|19|-4]]|1E|$5|14|15|16|A|$17|1F|19|-4]]|1G|$5|14|15|16|A|$17|1H|19|-4]]]]

One way to approach the problem can be to compare the rate of growth of O(<a href="https://i.stack.imgur.com/KfHDK.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/KfHDK.png" alt="sqrt(n)" /></a>) 
and O( <a href="https://i.stack.imgur.com/vb49G.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/vb49G.png" alt="log(n)" /></a>)
<ol>
<li><a href="https://i.stack.imgur.com/C9IRy.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/C9IRy.png" alt="derivative of sqrt n " /></a>
</li>
<li><a href="https://i.stack.imgur.com/D5eTi.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/D5eTi.png" alt="enter image description here" /></a>
</li>
</ol>
As n increases we see that (2) is less than (1). When n = 10,000 eq--1 equals 0.005 while eq--2 equals 0.0001
Hence <a href="https://i.stack.imgur.com/Txnre.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Txnre.png" alt="log(n)" /></a> is better as n increases.

blocks|key|602415|text|不，它们不是等价物，你甚至可以证明|type|unstyled|depth|inlineStyleRanges|entityRanges|data|602416|+++O(n**k)+>+O(log(n,+base))+|code-block|syntax|javascript|602417|用于任何k+>+0和base+>+1+(k+=+1/2在sqrt的情况下)。|offset|length|style|CODE|602418|在讨论O(f(n))时，我们要研究大n的行为，极限是很好的方法。假设两个大O是等价的：|602419|++O(n**k)+=+O(log(n,+base))+|602420|这意味着有一个有限的常数C|602421|++O(n**k)+<=+C+*+O(log(n,+base))+|602422|从一些足够大的n开始；用其他术语来表示它(log(n,+base)不是从大n开始的0，这两个函数都是连续可微的)：|602423|++lim(n**k/log(n,+base))+=+C+
++n->%2Binf|602424|为了求出极限值，我们可以使用L‘’Hospital规则，即以导数作为分子和分母，并将它们分开：|602425|++lim(n**k/log(n))+=+

++lim([k*n**(k-1)]/[ln(base)/n])+=

++ln(base)+*+k+*+lim(n**k)+=+%2Binfinity|602426|因此，我们可以得出结论，不存在像C这样的常量O(n**k)+<+C*log(n,+base)，或者换句话说|602427|+O(n**k)+>+O(log(n,+base))+|602428|entityMap|0|LINK|mutability|MUTABLE|url|http://mathworld.wolfram.com/LHospitalsRule.html^0|0|0|4|5|A|8|K|7|S|4|0|3|7|I|1|11|1|0|0|C|1|0|0|7|1|L|C|11|1|15|1|0|0|E|D|0|0|0|G|1|M|O|0|0^^$0|@$1|2|3|4|5|6|7|1E|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|1F|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|1G|8|@$I|1H|J|1I|K|L]|$I|1J|J|1K|K|L]|$I|1L|J|1M|K|L]|$I|1N|J|1O|K|L]]|9|@]|A|$]]|$1|M|3|N|5|6|7|1P|8|@$I|1Q|J|1R|K|L]|$I|1S|J|1T|K|L]|$I|1U|J|1V|K|L]]|9|@]|A|$]]|$1|O|3|P|5|D|7|1W|8|@]|9|@]|A|$E|F]]|$1|Q|3|R|5|6|7|1X|8|@$I|1Y|J|1Z|K|L]]|9|@]|A|$]]|$1|S|3|T|5|D|7|20|8|@]|9|@]|A|$E|F]]|$1|U|3|V|5|6|7|21|8|@$I|22|J|23|K|L]|$I|24|J|25|K|L]|$I|26|J|27|K|L]|$I|28|J|29|K|L]]|9|@]|A|$]]|$1|W|3|X|5|D|7|2A|8|@]|9|@]|A|$E|F]]|$1|Y|3|Z|5|6|7|2B|8|@]|9|@$I|2C|J|2D|1|2E]]|A|$]]|$1|10|3|11|5|D|7|2F|8|@]|9|@]|A|$E|F]]|$1|12|3|13|5|6|7|2G|8|@$I|2H|J|2I|K|L]|$I|2J|J|2K|K|L]]|9|@]|A|$]]|$1|14|3|15|5|D|7|2L|8|@]|9|@]|A|$E|F]]|$1|16|3|-4|5|6|7|2M|8|@]|9|@]|A|$]]]|17|$18|$5|19|1A|1B|A|$1C|1D]]]]

No, they are not equivalent; you can even prove that

<pre><code> O(n**k) &gt; O(log(n, base)) 
</code></pre>

for any <code>k &gt; 0</code> and <code>base &gt; 1</code> (<code>k = 1/2</code> in case of <code>sqrt</code>). 

When talking on <code>O(f(n))</code> we want to investigate the behaviour for large <code>n</code>, 
limits is good means for that. Suppose that both big <code>O</code> are equivalent:

<pre><code> O(n**k) = O(log(n, base)) 
</code></pre>

which means there's a some finite constant <code>C</code> such that 

<pre><code> O(n**k) &lt;= C * O(log(n, base)) 
</code></pre>

starting from some large enough <code>n</code>; put it in other terms (<code>log(n, base)</code> is not <code>0</code> starting from large <code>n</code>, both functions are continuously differentiable):

<pre><code> lim(n**k/log(n, base)) = C 
 n-&gt;+inf
</code></pre>

To find out the limit's value we can use <a href="http://mathworld.wolfram.com/LHospitalsRule.html" rel="nofollow noreferrer">L'Hospital's Rule</a>, i.e. take derivatives for numerator and denominator and divide them:

<pre><code> lim(n**k/log(n)) = 

 lim([k*n**(k-1)]/[ln(base)/n]) =

 ln(base) * k * lim(n**k) = +infinity
</code></pre>

so we can conclude that there's no constant <code>C</code> such that <code>O(n**k) &lt; C*log(n, base)</code> or in other words

<pre><code> O(n**k) &gt; O(log(n, base)) 
</code></pre>

blocks|key|1676967|text|不，它不是。当我们处理时间复杂性时，我们认为输入是一个非常大的数字。所以让我们取n=+2%5E18，现在对于sqrt(n)的运算数是2%5E9，对于log(n)，它将等于18+(我们这里考虑的是带2基的log+)。很明显，2%5E9远大于18。所以，我们可以说O(log+n)小于O(sqrt+n)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1676968|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

No, it isn't. 
When we are dealing with time complexity, we think of input as a very large number. So let's take n = 2^18. Now for sqrt(n) number of operation will be 2^9 and for log(n) it will be equal to 18 (we consider log with base 2 here). Clearly 2^9 much much greater than 18.
So, we can say that O(log n) is smaller than O(sqrt n).

blocks|key|1677116|text|为了证明sqrt(n)比lgn(base2)增长更快，可以在1的时间内取2的极限，并证明当n接近无穷大时，它接近0。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1677117|lim(n—>inf)+of+(lgn/sqrt(n))|code-block|syntax|javascript|1677118|适用L‘’Hopitals规则：|1677119|=+lim(n—>inf)+of+(2/(sqrt(n)*ln2)) |1677120|由于sqrt(n)和ln2将随着n的增加而无限增加，并且2是一个常数，这证明了|1677121|lim(n—>inf)+of+(2/(sqrt(n)*ln2))+=+0|1677122|entityMap^0|4|7|D|9|0|0|0|0|2|7|A|3|G|1|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@$9|V|A|W|B|C]|$9|X|A|Y|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|Z|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|10|8|@]|D|@]|E|$]]|$1|M|3|N|5|H|7|11|8|@]|D|@]|E|$I|J]]|$1|O|3|P|5|6|7|12|8|@$9|13|A|14|B|C]|$9|15|A|16|B|C]|$9|17|A|18|B|C]]|D|@]|E|$]]|$1|Q|3|R|5|H|7|19|8|@]|D|@]|E|$I|J]]|$1|S|3|-4|5|6|7|1A|8|@]|D|@]|E|$]]]|T|$]]

To prove that <code>sqrt(n)</code> grows faster than l<code>gn(base2)</code> you can take the limit of the 2nd over the 1st and proves it approaches 0 as n approaches infinity.
<pre><code>lim(n—&gt;inf) of (lgn/sqrt(n))
</code></pre>
Applying L’Hopitals Rule:
<pre><code>= lim(n—&gt;inf) of (2/(sqrt(n)*ln2)) 
</code></pre>
Since <code>sqrt(n)</code> and <code>ln2</code> will increase infinitely as <code>n</code> increases, and 2 is a constant, this proves
<pre><code>lim(n—&gt;inf) of (2/(sqrt(n)*ln2)) = 0
</code></pre>

My professor just taught us that any operation that halves the length of the input has an O(log(n)) complexity as a thumb rule. Why is it not O(sqrt(n)), aren't both of them equivalent?

Is complexity O(log(n)) equivalent to O(sqrt(n))?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

我的教授刚刚告诉我们，任何将输入长度减半的操作都有O(log(n))复杂性，这是一个经验法则。为什么不是O(sqrt(n))，两者不是等价的？

问复杂度O(log(n))是否等价于O(sqrt(n))？
EN

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问复杂度O(log(n))是否等价于O(sqrt(n))？EN

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问复杂度O(log(n))是否等价于O(sqrt(n))？
EN