sat*_*res 2 arrays algorithm complexity-theory
我想知道如何对本例计算为O(log(N)):我们有10种元素[1 3 4 8 10 15 18 20 25 30]的排序后的数组当我们在普通搜索,我们有一个的复杂性O(10)这意味着我们必须检查阵列所以O(10)= 10的每一种情况下,但如果我们做一个二分搜索,因为我们有一个排序后的数组,我们有一个的复杂度(O(日志(10))什么是这种符号的结果O(Log(10))= ???？我有一个误解我们应该使用Log base 10或2还是究竟是什么？感谢您的帮助
Ama*_*ony 13
您误解了算法增长顺序的概念.请阅读一本关于算法的书,让你的概念变得强大.在任何情况下,我都会尝试高级解释,
如果你有10个元素的数组像你说的,你做一个"正常的搜索"(这就是所谓的线性搜索)您是通过数组中的每个元素,这意味着迭代,如果有"N"元素"N"元素必须检查.所以它是O(n)而不是O(10).如果它是O(10)[btw,O(10)= O(1)]意味着它总是需要10次或更少次迭代,无论数组中有多少元素,情况都不是这样的.如果你的数组有100个元素,那么需要100次迭代,所以我们说顺序是O(n),其中n是输入大小(这里是数组的大小).
上面的方法用于非排序数组,对于排序数组,我们可以使用更快的方法进行搜索,就像在字典中查找单词一样,这种技术称为二进制搜索.这里发生的是,你查找数组的中间元素,看看你要搜索的数字在哪里,在上半部分或下半部分.然后,选择所需的一半,并应用相同的方法将其分成两半并进行检查.由于这是递归完成的,因此它使用对数增长(在二进制搜索的情况下,它是log 2到base 2).请阅读二进制搜索和对数增长顺序,以便更好地理解.
我认为您对二进制搜索为什么是log（n）及其基数2感到困惑。以这种方式思考，在二进制搜索的每一步中，您都将输入大小减小了2。去做这个 ？您需要将此log n记录到基数上两次，以将样本大小减小到1。
例如，如果您有4个元素，则第一步将搜索减小到2，第二步将搜索减小到1，然后停止。因此，您必须将日志（4）记录到基数2 = 2次。换句话说，如果log n以2为底，则x升为2的幂为n。
因此，如果执行二进制搜索，则基数将为2。更清楚的是，在您的情况下，Log（10）基数2约为3.3，即，您最多将进行4次比较。