-3

以下程序的时间复杂度是多少？

sum=0;
for(i=1;i<=5;i++)
 sum=sum+i;

以及如何在日志中定义这种复杂性？如果有人逐步解释复杂性，我将不胜感激。此外如何在 O(big o) 和 logn 中显示。

[已编辑]

sum=0; //1 time
i=1;   //1 time
i<=5;  //6 times
i++    //5 times
sum=sum+i;//5 times

时间复杂度是 18 吗？正确的？

4

2 回答 2

2

预赛

时间复杂度通常不以特定整数表示，因此“操作 X 的时间复杂度为 18”的陈述如果没有单位，例如 18“小玩意儿”就不清楚。

通常将时间复杂度表示为某个函数/操作的输入大小的函数。

由于硬件差异甚至不同语言之间常数因素的差异，您通常希望忽略特定操作所需的特定时间量。例如，求和仍然O(n)（通常）在 C 和 Python 中（您仍然必须执行n加法），但是两种语言之间常数因子的差异将导致 C 在操作停止的绝对时间方面更快。

人们通常还假设“Big-Oh”——例如，——O(f(n))是算法的“最坏情况”运行时间。还有其他符号用于研究更严格的上限和下限。

你的问题

不是从 1 到 5 求和，而是从 1 到 求和n。

其复杂性在于O(n)您n要加在一起的元素数量。

每次添加 (with ) 都需要恒定的时间，在这种情况下+，您需要花费时间。n

但是，您展示的这个特定操作可以在O(1)（恒定时间）内完成，因为从 1 到的数字之和n可以表示为单个算术运算。我会把细节留给你自己弄清楚。

至于用对数表达这一点：不完全确定你为什么想要，但这里有：

因为exp(log(n))is n，您可以将其表示为O(exp(log(n)))。你为什么想做这个？O(n)完全可以理解，无需调用logor exp。

于 2013-10-20T18:05:46.907 回答
0

首先，循环针对 5 个输入运行 5 次，因此它的时间复杂度为 O(n)。我在这里假设 i 中的值是 sum 的输入。其次，您不能只用对数术语定义时间复杂度，它应该始终使用 BIG O 表示法。例如，如果您执行二进制搜索，则该算法的最坏情况时间复杂度为 O(log n)，因为当输入数组为 8 时，您会得到 3 次迭代的结果。

复杂度 = log2(base)8 = 3

现在你的复杂性在日志中。

于 2013-10-20T18:08:02.713 回答