blocks|key|477094|text|看看输入大小和计算时间的商。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|477095|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|$]]

Look at the quotients of the input sizes and the computing times.

blocks|key|1674825|text|给出这三种算法的性能图--时间复杂度将变得明显。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1674826|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|$]]

Graph the performance of the three algorithms - the time complexity will then become obvious.

blocks|key|1674836|text|确保您理解了术语nlogn、n%5E2和n。考虑绘制此函数，以了解输入与其输出之间的关系。如果你理解这些关系，答案将是显而易见的。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1674837|entityMap^0|8|5|E|3|I|1|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]|$9|M|A|N|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|O|8|@]|D|@]|E|$]]]|G|$]]

Make sure you understand the terms <code>nlogn</code>, <code>n^2</code> and <code>n</code>. Consider plotting this functions to understand the relationship between input and their output. The answer will be obvious if you understand these relationships.

blocks|key|477164|text|很多时候，我发现比较复杂的最简单的方法是将结果“正常化”。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|477165|Input+Size:++++++1+++++++2++++++4
Algorithm+A:+++++1++++++1.91+++3.74
Algorithm+C:+++++1++++++2.04+++4.33
Algorithm+B:+++++1++++++3.82++15.21|code-block|syntax|javascript|477166|该表是通过将每一行按其最小值(本例中的第一个元素)来获得的。|477167|然后，我重新排序了从缓慢增长到快速增长的直线:你能猜出每种算法的复杂性吗？|477168|PS：n+log+n的备忘单，只是为了验证近似|offset|length|style|CODE|477169|Input+Size+++++++Time
n++++++++++++++++n+log+n
2*n++++++++++++++2+*+n+*+(log+n+%2B+log+2)
4*n++++++++++++++4+*+n+*+(log+n+%2B+2+*+log+2)|477170|entityMap^0|0|0|0|0|3|7|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|W|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|X|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|Y|8|@$M|Z|N|10|O|P]]|9|@]|A|$]]|$1|Q|3|R|5|D|7|11|8|@]|9|@]|A|$E|F]]|$1|S|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|T|$]]

Often times, I have found that the easiest way to compare complexities was to "normalize" the results.

<pre><code>Input Size: 1 2 4
Algorithm A: 1 1.91 3.74
Algorithm C: 1 2.04 4.33
Algorithm B: 1 3.82 15.21
</code></pre>

This table is simply obtained by divising each line by its minimum (the first element in this case).

I have then re-ordered the lines from the slow-growing one to the fast-growing one: can you guess the complexity of each of the algorithms ?

PS: the cheat sheet for <code>n log n</code>, just to verify the approximations

<pre><code>Input Size Time
n n log n
2*n 2 * n * (log n + log 2)
4*n 4 * n * (log n + 2 * log 2)
</code></pre>

blocks|key|477190|text|这个问题让我感到惊讶:有些老师会问这样的虚假和误导的问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|477191|(+1)当O(n)，O(nlogn)，O(n%5E2)实际上是指Theta(n)，Theta(nlogn)和Theta(n%5E2)时，这个问题是否真的涉及到O(N)，O(n%5E2)？|477192|2)|477193|仅仅三个数据点(或9个总数)不足以区分哪个数据点。|477194|我们可以选择合适的常量，这样A，B，C就可以是我们想要的三个常数中的任何一个。|477195|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

This question leaves me surprised: that there are teachers who ask such kind of bogus and misleading questions.

1) Did the question really talk about O(n), O(nlogn), O(n^2) when they really mean Theta(n), Theta(nlogn) and Theta(n^2)?

2)

Just three data points (or 9 total) is not sufficient to distinguish which is which.

We can choose the appropriate constants so that A,B,C could be any of the three we want.

blocks|key|1674848|text|绘制3个数据集的图表。比较了n，n，nlogn图的增长速度。你会看到的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1674849|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|$]]

Draw the graphs of the 3 dataset. Compare with the growth rate of the graphs for n, nlogn...
You will see.

For a given problem with input size n, Algorithms A,B,C are executed. In terms of running time, one of the algorithms is O(n), one O(nlogn) and one O(n^2). Some measured running times of these algorithms are given below

<pre><code> Input Size
 512 1024 2048

 A 70 134 262 
 B 135 517 2053
 C 42 86 182
</code></pre>

Identify which algorithm is which and explain the observed running times. Which algorithm would you select for different values of n

Please help me with the above question.
Thanks

Identifying which Algorithm is which and explaining the running times

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

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

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

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

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

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

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

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

社区新版编辑器体验调研

对于输入大小为n的给定问题，算法A、B、C被执行。在运行时间方面，算法之一是O(n)、O(nlogn)和O(n^2)。下面给出了这些算法的一些实测运行时间。                            Input Size                    512         1024            2048            A        70         

问识别哪一种算法并解释运行时间
EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问识别哪一种算法并解释运行时间EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问识别哪一种算法并解释运行时间
EN