blocks|key|3263263|text|C就是这样，一个常数。这意味着您不能说“让c是n的值”，因为您必须首先选择一些c，然后允许对所有n进行比较。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3263264|换句话说，为了使某些T(+n+)是O(G(n))，不存在常数c使得G(n)*c对所有n都大于T(n)。|3263265|因此，not不是O(log+)，因为无论您选择什么常数，n+>c都会导致not大于c。|3263266|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

c is just that, a constant. This means that you can't say "let c be the value of n", because you must choose some c first and then allow the comparison to hold for all n.

In other words, in order for some T(n) to be O(G(n)), there must exist no constant c such that G(n)*c is greater than T(n) for all n.

Thus n log n is not O(log n) because, no matter what constant you choose, n > c will cause n log n to be greater than c log n.

blocks|key|947214|text|让我重复一遍你的话。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|947215|947216|+c可以是任何常量。|blockquote|offset|length|style|BOLD|947217|947218|947219|这意味着c不能依赖于n。|947220|entityMap^0|0|0|7|2|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|R|8|@$F|S|G|T|H|I]]|9|@]|A|$]]|$1|J|3|-4|5|6|7|U|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|V|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|W|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|X|8|@]|9|@]|A|$]]]|O|$]]

Let me repeat your words.

<blockquote>
 c can be any constant.
</blockquote>

This means that c can not depend on n.

blocks|key|4730903|text|这个想法是，对于任何n和固定的c，不等式都成立。因此，当你可能找到某个c使得doesn<+can，(即任何c>n)时，你可以很容易地找到它不成立的其他n‘(即n'>c).|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4730904|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|$]]

the idea is that the inequality holds for any n and a fixed c. so while you might find a certain c such that n log n &lt; c log n, (namely any c>n), you can easily find other n' for which it doesn't hold (namely n'>c).

blocks|key|3263400|text|首先，如果是n=C，那么C不是常量。在大多数现实世界的算法中，C很小，因此对于n的典型值，大O部分通常占主导地位。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3263401|但big-O复杂度与大n的算法效率有关，特别是当n接近无穷大时。换句话说，它告诉您算法的可伸缩性:给定的算法处理非常大或加倍的工作负载的能力。|3263402|如果你知道n总是小的，那么大O复杂度并不那么重要，相反，你应该关注算法所需的挂钟时间。此外，如果您在具有相同大O复杂度(例如O(n+log+n))的两种算法之间进行选择，则通常其中一种算法比另一种算法更好(例如随机轴心快速排序通常优于二进制堆排序)。|3263403|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

First of all, if n=C then C is not a constant. And in most real-world algorithms, C is small so the big-O part usually dominates for typical values of n.

But big-O complexity is concerned with the efficiency of an algorithm for large n, especially as n approaches infinity. In other words it tells you the scalability of an algorithm: how well a given algorithm handles a very large or doubled workload.

If you know that n is always small then the big-O complexity is not that important, rather you should focus on the wall-clock time required by the algorithm. Also, if you are choosing between two algorithms that have the same big-O complexity (e.g. O(n log n)), quite often one is better than the other (e.g. random-pivot quicksort generally outperforms a binary heap sort).

blocks|key|947256|text|在定义中，您应该仅通过T和G本身来确定C。这就是常量C的含义。所以C不应该依赖于它们的输入。所以你不能考虑C=n|type|unstyled|depth|inlineStyleRanges|entityRanges|data|947257|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|$]]

In the definition you should determine C just by the T and G themselves. This is what a constant C means. So C should not depend on the input of them. So you can not consider C = n

blocks|key|4730935|text|在表达式n+log+n中，您不能像现在这样将外部n与C进行比较。这就好比取代数表达式x(x%2B1)，然后用一个常量替换其中一个x。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4730936|在n+log+n中，n是一个变量。在大的O表达式中，C是一个常数。|4730937|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

in the expression n log n, you can't compare the outside n to C, like you are doing. That would be like taking the algrebraic expression x(x+1) and replacing one of the x's with a constant. 

In n log n, n is a variable. In the big O expresion, C is a constant.

blocks|key|1069659|text|N的值取决于输入集合，C的值是固定的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1069660|所以，是的，如果n=+16，C=+256，对于一个小的输入集，它看起来像n%5E2+*+lg(n)。现在将输入集增加到100,000,000；C的值保持为256，您现在有256+*+lg+(100,000,000)|1069661|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

The value of n depends on the input set, the value of C is fixed. 

So yes, if n = 16 and C = 256, it looks like n^2 * lg(n) for a small input set. Now increase the input set to 100,000,000; the value of C stays at 256, you now have 256 * lg (100,000,000)

blocks|key|3263442|text|每当我被big-oh困扰时，我发现把它看作是一场竞赛是很有用的:我选择一个big-oh函数(所以，在您的例子中是logn)和一个常量(c)。重要的是，我必须选择一个真正的值。我通常会挑一千个，只是因为。那我就得让我的死对头挑任何他想要的。他通常会选择十亿美元。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3263443|然后我进行比较。|3263444|为了完成示例，10%5E9*(log(10%5E9))现在明显大于1000log(10%5E9)。因此，我知道大-哦不会起作用。|3263445|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Whenever I'm stuck on big-oh, I find it useful to think of it as a competition:
I choose a big-oh function (so, in your case, logn) and a constant (c). The important thing is that I have to choose a real value. I usually pick a thousand, just because.
Then I have to let my arch-nemesis pick any n he chooses. He typically chooses a billion.

Then I make the comparison.

To finish the example, 10^9*(log(10^9)) is now made clearly much bigger than 1000log(10^9). Thus, I know that the big-oh won't work.

I've been having some problems trying to grasp the concept of big O notation. So, by definition big O is as follows, <code>T(n) ∈ O(G(n)) if T(n) &lt;= G(n) * C</code>. 

Since the the constant "C" can be any integer > 0, wouldn't this following example be true as well?

Example:

<pre><code>n log n ∈ O(log n)
n log n &lt;= log n * c
</code></pre>

Where C is equal to the value of n.

I know that the answer is that <code>n log n ∉ O(log n)</code> but I don't understand how since C can be any constant.

Thanks in advance for your help :D

Help with big O notation

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

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

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

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

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

我在尝试理解大O符号的概念时遇到了一些问题。因此，大O的定义如下所示，T(n) ∈ O(G(n)) if T(n) <= G(n) * C。既然常量"C“可以是大于0的任何整数，下面的例子不也是正确的吗？示例：n log n ∈ O(log n)n log n <= log n * c其中C等于n的值。我知道答案是n log n ∉ O(log n)，但我不明白为什么，因为C可以是任何常数。提前感

问帮助使用大O符号
EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问帮助使用大O符号EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问帮助使用大O符号
EN