是什么小于n是log n？

Question

考虑问题有两种解决方案。

1. 执行N/2倍，即。如果n = 100，则执行50次
2. 以n次sqrt执行，即。如果n = 100，则执行10次。

这两种解决方案都可以称为O（log N）？

如果是这样，则存在的N和N/2之间的sqrt巨大的差异。

如果我们不能说O（日志N），那么我们可以说，这是N？

但问题是这两者之间的差异率。通过下面的图片算法应该出现在这些东西之中，这些解决方案将在哪些方面出现？

请帮我在这。

Answer 1

考虑三种情况。

1. 执行n/2次。这意味着每一个我们通过因子100，通过100

2. 执行sqrt(n)倍的因子的执行时间的增加加N时间。这意味着每次我们将n增加100倍，执行时间增加10倍。

3. 执行log(n)次。这意味着每次我们将n增加100倍，执行时间就会增加一个常量。

不，这三件事情甚至都没有接近。第一个比第二个糟糕得多。第三个比第二个好得多。

Answer 2

他们都不是O(logn)

这里是O(logn)一个例子，Binary search algorithm

Answer 3

最好的算法是，你有数据的最佳算法。如果你不知道你有什么数据，请考虑大量的数据，比如n = 10亿。你会选择O（31623）还是O（5000000000）？绘制比较图并找到您的数据大小。

如果您的数据集是n = 4，那么任一算法都是相同的。如果您了解细节，由于它执行的操作，实际上可能需要较长的时间才能执行sqrt（n）算法。

你可以有O（1）这是最快的。一个这样的例子是查找哈希映射，但是你的内存大小可能会受到影响。所以你应该考虑空间限制和时间限制。

您也在误解和过分分析复杂性分类。 O（n）算法不是用正好n个操作执行的算法。任何常数乘数不会影响分类的顺序。问题增长时，操作次数的增长非常重要。考虑两种搜索算法。

A) Scan a sorted list sequentially from index 0 to (n-1) to find the number. 

B) Scan a sorted list from from index 0 to (n-1), skipping by 2, and backtracking if necessary. 

显然需要至多n个操作，和B需要N/2 + 1的操作。然而他们都是O（n）。你可以说算法B更快，但我可以在我的机器上运行它，速度是它的两倍。所以复杂性是一个普通的阶级，人们不应该对操作的细节过分挑剔。

如果你试图建立一个更好的算法，它会更加有用与略少操作寻找一个具有更好的复杂性类，不止一个。