简单的时间复杂度计算

Question

我是新来的时间复杂性，现在开始解决问题， 我不确定我是否正确，请告诉我，如果我这样做，如果没有， 如何计算它。

我计算的最坏情况下6n+5，而一般情况下，O(n)，是正确的吗？

Answer 1

采取最常执行的指令。这是num = Random.Next (100)（与其他人并列）。它多久执行一次？ N次;它是O（N）。

您也可以使用其他指令的频率。我们会看到这并不重要。如果你这样做，你会得到O（6N + 5），或者类似的东西（因为没关系，我会把你的数量计算在内）。

如果你有东西加在一起，只保留最大的一个（当N很大时）。当N很大时，6N> 5，所以你只需保持O（6N）。

丢弃恒定乘数。所以你保留N并得到O（N）。

因为我们只关心大的N会发生什么，所以我们放弃了大N最大的一个。对于大的N，小的东西变得微不足道。

我们抛弃了常数乘法器，因为我们不关心精确的指令数量，而只是：当您将N的大小加倍时，时间会发生什么变化？当我们三倍，四倍，你有什么，N的大小，会发生什么？无论乘以6还是任何其他常数都无关紧要 - 所以我们放弃了不变的乘数。

Answer 2

是，否。它在O(n)中，因为您重复for循环n次。作业和声明是O(1) - 不变。我不知道你从哪里拍了6n + 5。前三行只完成一次。在最坏情况下，循环重复n次，每个数字大于参数。所以你有4*O(1)。由于最后一条语句不在循环之中，因此它只执行一次。总计3 + 4*n + 1 = 4n + 4。占主导地位的是4n，删除常数，你得到O(n)时间。

通过主导术语的意思，对于n到无穷大，真的没有，如果你通过2,3,4乘以或其他一些数除以它，这当然适用于一些非常大的数字，因为没有无限事与电脑。