blocks|key|4054789|text|如果您只改进了常量，则需要提供具体的计时统计信息。大O符号仅用于渐近行为。例如，您需要指定一组给定的测试数据，并显示优化后的版本比未优化的版本快X%25或X倍。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4054790|您还没有改进实现的渐近行为，因为原始版本和优化版本都运行在O(n)时间内。|4054791|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|$]]

If you have only improved on the constant, you'll need to provide concrete timing statistics. Big-O notation is only for asymptotic behavior. For example, you'll need to specify a given set of test data, and show that your optimized version is X% or X times faster than the unoptimized version.

You have not improved the asymptotic behavior of the implementation, as both the original and the optimized version run in O(n) time.

blocks|key|4054820|text|例如，9001n%5E2算法和n%5E2算法都是大O(n%5E2)，但是其中一个算法的速度要快9001倍。因此，从第一个到第二个减少了9001倍的运行时间。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4054821|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 complexity of the algorithm would have stayed the same, but you've reduced the runtime by a factor of x. So for example, an 9001n^2 algorithm and an n^2 algorithm are both big O(n^2), but one is 9001 times faster. Thus, going from the first to the second decreases the runtime by a factor of 9001.

blocks|key|1737920|text|O(n)+=+O(n)，所以不能说大O复杂度的变化，因为大O复杂度没有变化。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1737921|您可以简单地说，运行时间缩短了X倍或某个百分比，或者您也可以使用~-notation。|offset|length|1737922|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations^0|0|W|A|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

O(n) = O(n), so no, you can't say anything about a change to the big-O complexity, since the big-O complexity didn't change.

You can simply say that the running time improved by a factor of X or by some percentage, or perhaps you could use <a href="http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations" rel="nofollow">~-notation</a>.

blocks|key|5523486|text|This+(deleted)+question是优化改变渐近复杂性的一个很好的例子。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|5523487|这不是关于排序，但它确实解决了您提出的整个问题，所以我将在这里重现答案，给出一个可以在Big-O表示法中看到优化的示例：|5523488|5523489|TL;DR+:需要测量运行时，而不是“计算”。|5523490|5523491|运行时高度依赖于编译器。我使用三个非常流行的C%2B%2B编译器在优化级别2下进行了测试，没有对整个程序进行优化。一个给出立方运行时，两个给出线性运行时。根据使用的是amd64还是x86编译器，微软占据了最好和最差的位置。|5523492|我使用i=+1，10,100,200,1000,2000,10000,20000和足够的迭代次数来运行，至少需要2秒。时间是根据我的性能计数器的频率报告的，而不是以秒为单位，但是时基是稳定的，所以它和其他时间一样好。这是一个核心i5哈斯韦尔，如果有人关心。|5523493|使用Visual+Studio+2013更新3，x86编译|5523494|timing+unit+is+2240908.000000+per+second
i+++++++iterations++++++elapsed+time
1+++++++1000000000++++++7974255
10++++++100000000+++++++40455055
100+++++100000++++++++++30560052
200+++++10000+++++++++++24365172
1000++++100+++++++++++++30615626
2000++++10++++++++++++++24530866|code-block|syntax|javascript|5523495|​|5523496|📷|atomic|5523497|5523498|使用Visual+Studio+2013更新3，x64编译|5523499|timing+unit+is+2240908.000000+per+second
i+++++++iterations++++++elapsed+time
1+++++++1000000000++++++6123844
10++++++1000000000++++++29860683
100+++++100000000+++++++25790181
200+++++10000000++++++++4977144
1000++++10000000++++++++23488811
2000++++1000000+++++++++4750398
10000+++1000000+++++++++23544227
20000+++100000++++++++++4726392|5523500|使用cygwin+g%2B%2B+4.8.2，64位编译|5523501|timing+unit+is+2240908.000000+per+second
i+++++++iterations++++++elapsed+time
1+++++++1000000000++++++6460830
10++++++1000000000++++++25768266
100+++++100000000+++++++30732123
200+++++10000000++++++++6294949
1000++++10000000++++++++31590581
2000++++1000000+++++++++6206729
10000+++1000000+++++++++31528696
20000+++100000++++++++++6217971|5523502|5523503|5523504|5523505|以下是基准测试驱动程序：|5523506|#include+<windows.h>
#include+<stdio.h>

extern+long+long+the_function(int+i);

int+main(int+argc,+char**+argv)
{
++++LARGE_INTEGER+timing_freq;
++++QueryPerformanceFrequency(&timing_freq);
++++printf("timing+unit+is+%25f+per+second\n",+(double)timing_freq.QuadPart);

++++for(+int+a+=+1;+a+<+argc;+%2B%2Ba+)+{
++++++++char*+pEnd;
++++++++int+i+=+strtoul(argv[a],+&pEnd,+0);
++++++++if+(*pEnd)+{
++++++++++++printf("Couldn't+understand+\'%25s\'\n",+argv[a]);
++++++++++++return+1;
++++++++}

++++++++LARGE_INTEGER+before;
++++++++LARGE_INTEGER+after;
++++++++long+long+iterations+=+1;
++++++++do+{
++++++++++++iterations+*=+10;
++++++++++++QueryPerformanceCounter(&before);
++++++++++++for(+int+k+=+0;+k+<+iterations;+%2B%2Bk+)
++++++++++++++++the_function(i);

++++++++++++QueryPerformanceCounter(&after);
++++++++}+while+(after.QuadPart+-+before.QuadPart+<+2+*+timing_freq.QuadPart);

++++++++printf("%25d\t%25lld\t%25lld\n",+i,+iterations,+after.QuadPart+-+before.QuadPart);
++++}

++++return+0;
}|5523507|和被评估的代码：|5523508|long+long+the_function(int+i)
{
++++long+long+x+=+0;
++++for(int+n+=+0;+n+<+i;+n%2B%2B)
++++++++for+(int+j+=+0;+j+<+n*n;+j%2B%2B)
++++++++++++x%2B%2B;
++++return+x;
}|5523509|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/q/25756686/103167|1|IMAGE|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/d83a1ad37ef6d8d2c806a2b0c2e35f4a.png|imageAlt|2|https://ask.qcloudimg.com/http-save/yehe-900000/fd629cac61ded747c63fda757ce50728.png^0|0|N|0|0|0|0|0|0|0|0|0|0|0|0|1|1|0|0|0|0|0|0|0|0|1|2|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1Z|8|@]|9|@$A|20|B|21|1|22]]|C|$]]|$1|D|3|E|5|6|7|23|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|24|8|@]|9|@]|C|$]]|$1|G|3|H|5|6|7|25|8|@]|9|@]|C|$]]|$1|I|3|-4|5|6|7|26|8|@]|9|@]|C|$]]|$1|J|3|K|5|6|7|27|8|@]|9|@]|C|$]]|$1|L|3|M|5|6|7|28|8|@]|9|@]|C|$]]|$1|N|3|O|5|6|7|29|8|@]|9|@]|C|$]]|$1|P|3|Q|5|R|7|2A|8|@]|9|@]|C|$S|T]]|$1|U|3|V|5|6|7|2B|8|@]|9|@]|C|$]]|$1|W|3|X|5|Y|7|2C|8|@]|9|@$A|2D|B|2E|1|2F]]|C|$]]|$1|Z|3|V|5|6|7|2G|8|@]|9|@]|C|$]]|$1|10|3|11|5|6|7|2H|8|@]|9|@]|C|$]]|$1|12|3|13|5|R|7|2I|8|@]|9|@]|C|$S|T]]|$1|14|3|15|5|6|7|2J|8|@]|9|@]|C|$]]|$1|16|3|17|5|R|7|2K|8|@]|9|@]|C|$S|T]]|$1|18|3|V|5|6|7|2L|8|@]|9|@]|C|$]]|$1|19|3|X|5|Y|7|2M|8|@]|9|@$A|2N|B|2O|1|2P]]|C|$]]|$1|1A|3|V|5|6|7|2Q|8|@]|9|@]|C|$]]|$1|1B|3|1C|5|6|7|2R|8|@]|9|@]|C|$]]|$1|1D|3|1E|5|R|7|2S|8|@]|9|@]|C|$S|T]]|$1|1F|3|1G|5|6|7|2T|8|@]|9|@]|C|$]]|$1|1H|3|1I|5|R|7|2U|8|@]|9|@]|C|$S|T]]|$1|1J|3|-4|5|6|7|2V|8|@]|9|@]|C|$]]]|1K|$1L|$5|1M|1N|1O|C|$1P|1Q]]|1R|$5|1S|1N|1T|C|$1U|1V|1W|-4]]|1X|$5|1S|1N|1T|C|$1U|1Y|1W|-4]]]]

<a href="https://stackoverflow.com/q/25756686/103167">This (deleted) question</a> was a good example of optimization changing the asymptotic complexity.

It's not about sorting, but it does address the overall question you asked, so I'll reproduce the answer here, to give an example where optimization can be seen in Big-O notation:

<hr>

TL;DR : Runtime needs to be measured, not "computed".

<hr>

The runtime is HIGHLY compiler dependent. I tested with three very popular C++ compilers under optimization level 2 and no whole program optimization. One gave cubic runtime and two gave linear runtime. Microsoft holds both best and worst places, depending on whether the amd64 or x86 compiler is used.

I ran using i = 1, 10, 100, 200, 1000, 2000, 10000, 20000 and enough iterations to take at least two seconds. The times are reported against the frequency of my performance counter, not in seconds, but the timebase is steady so it's as good as any other. This is a Core i5 Haswell if anyone cares.

Using Visual Studio 2013 Update 3, x86 compilation

<pre><code>timing unit is 2240908.000000 per second
i iterations elapsed time
1 1000000000 7974255
10 100000000 40455055
100 100000 30560052
200 10000 24365172
1000 100 30615626
2000 10 24530866
</code></pre>

<img src="https://i.stack.imgur.com/YFpJD.png" alt="cubic runtime from MSVC in 32-bit mode">

Using Visual Studio 2013 Update 3, x64 compilation

<pre><code>timing unit is 2240908.000000 per second
i iterations elapsed time
1 1000000000 6123844
10 1000000000 29860683
100 100000000 25790181
200 10000000 4977144
1000 10000000 23488811
2000 1000000 4750398
10000 1000000 23544227
20000 100000 4726392
</code></pre>

Using cygwin g++ 4.8.2, 64-bit compilation

<pre><code>timing unit is 2240908.000000 per second
i iterations elapsed time
1 1000000000 6460830
10 1000000000 25768266
100 100000000 30732123
200 10000000 6294949
1000 10000000 31590581
2000 1000000 6206729
10000 1000000 31528696
20000 100000 6217971
</code></pre>

<img src="https://i.stack.imgur.com/rbaCE.png" alt="linear runtime from both 64-bit compilers">

Here's the benchmark driver:

<pre><code>#include &lt;windows.h&gt;
#include &lt;stdio.h&gt;

extern long long the_function(int i);

int main(int argc, char** argv)
{
 LARGE_INTEGER timing_freq;
 QueryPerformanceFrequency(&amp;timing_freq);
 printf("timing unit is %f per second\n", (double)timing_freq.QuadPart);

 for( int a = 1; a &lt; argc; ++a ) {
 char* pEnd;
 int i = strtoul(argv[a], &amp;pEnd, 0);
 if (*pEnd) {
 printf("Couldn't understand \'%s\'\n", argv[a]);
 return 1;
 }

 LARGE_INTEGER before;
 LARGE_INTEGER after;
 long long iterations = 1;
 do {
 iterations *= 10;
 QueryPerformanceCounter(&amp;before);
 for( int k = 0; k &lt; iterations; ++k )
 the_function(i);

 QueryPerformanceCounter(&amp;after);
 } while (after.QuadPart - before.QuadPart &lt; 2 * timing_freq.QuadPart);

 printf("%d\t%lld\t%lld\n", i, iterations, after.QuadPart - before.QuadPart);
 }

 return 0;
}
</code></pre>

And the code being evaluated:

<pre><code>long long the_function(int i)
{
 long long x = 0;
 for(int n = 0; n &lt; i; n++)
 for (int j = 0; j &lt; n*n; j++)
 x++;
 return x;
}
</code></pre>

I'm writing about an optimisation about an algorithm which has O(n) complexity. It still has O(n) complexity but the execution time has improved tremendously. Is it correct for me to say that I've improved the O part? If not, how can I refer to the speed of the algorithm?

Can I use Big-O notation to compare performance of optimised and unoptimised implementation of same algorithm?

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

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

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

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

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

我正在写一个关于O(n)复杂度的算法的优化。它仍然有O(n)的复杂度，但执行时间有了极大的改善。我说我改进了O部分，对吗？如果不是，我怎么才能提到算法的速度呢？

问我可以使用Big-O表示法来比较相同算法的优化和未优化实现的性能吗？
EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问我可以使用Big-O表示法来比较相同算法的优化和未优化实现的性能吗？EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问我可以使用Big-O表示法来比较相同算法的优化和未优化实现的性能吗？
EN