2

我需要推导出这个验证程序的大 O 符号。它的工作是接受这种类型的产品条目:'jacket,8,12,18,16,6',对其进行验证,对尺寸进行排序,按字母顺序将条目排序到列表中,并在每个条目之后打印新列表。

Big-O 表示法基于最坏情况,即程序执行特定输入所需的时间最长。采用 'parseData' 方法,最坏的情况是输入完全有效,因此不传递任何异常并执行所有方法。产品名称有 15 个字符,输入 5 种尺寸。在这种情况下,此方法和以下其他较小的验证方法将始终花费相同的时间来执行此最坏情况事件。如评论中所示,这给了他们 O(1) 的复杂性。

主要是有;- 验证 - O(n) - 排序 - O(nlogn) - 打印 - O(n^2)

这会归结为O(n ^ 2)吗?还是取决于所考虑的条目数量?

4

1 回答 1

0

对于渐近分析,它会归结为 O(n^2),因为它的增长速度比 O(n logn) 和 O(n) 快得多。但请注意,这只是一个渐近上限,这意味着它可能不是很紧,正如你所说,它是最坏的情况,而不是平均或预期的情况。

于 2013-01-20T13:16:32.453 回答