2

这个问题是关于解决方案之间是否存在一些抽象的相似性，导致出现排序和搜索等登录问题。或者，更简单地说，为什么 log 在算法复杂度中如此频繁地出现？

4

3 回答 3

6

当一个问题的大小可以通过乘法因子反复减小时，通常会出现对数。根据定义，将问题减小到恒定大小（例如大小 1）需要对数步数。

一个典型的例子是重复消除一半的数据集，就像在二分搜索中所做的那样。这带来了O(log2(n))复杂性。一些排序算法通过重复将数据集分成两半来工作，因此它们的时间复杂度也有对数项。

更一般地，对数经常出现在分治递归关系的解决方案中。有关进一步讨论，请参阅Wikipedia 中的Master Theorem。

于 2014-10-15T19:40:37.153 回答
0

由于布尔逻辑，日志在计算机科学中经常出现。一切都可以简化为true vs false或1 vs 0或to be 或 not to be。如果你有一个if陈述，你有一个选择，否则你有另一个选择。这可以应用于位（您有 0 或 1）或高影响问题，但有一个决定。就像在现实生活中一样，当你做出决定时，你并不关心如果你做出其他决定可能会发生的问题。这就是log 2 (n)经常出现的原因。

然后，每一种更复杂的情况（例如：从 3 个状态中选择一个可能的状态）都可以简化为log 2 (n) => 对数底无关紧要（常数不会影响函数的趋势 - 它具有相同的程度）：

  • 数学证明：

              loga(y)      1
logx(y) = ------- = -------- * loga(y) = constant * loga(y)
          loga(x)    loga(x)

  • 程序员的证明：

    switch(a) { 
    case 1: ... ;
    case 2: ... ;
    ...
    default: ... ;
}

    类似于：

    if (a == 1) {  
    ...
} else {
    if ( a == 2 ) {
        ...
    }
    ...
}

    （a switchfor koptions 等价于k-1 if-else语句，其中k= 常量）

但为什么要登录？因为它是指数的倒数。在第一个决定中，您将大问题分成两部分。然后你只把“好”的一半分成两部分，等等。

n      = n/2^0         // step 1
n/2    = n/2^1         // step 2
n/4    = n/2^2         // step 3
n/8    = n/2^3         // step 4
...
n/2^i  = n/2^i         // step i+1

问：有多少步？

A : i+1 (从 0 到 i )

因为当您找到想要的元素时它会停止（您无法做出其他决定）=> n = 2^i。如果我们应用对数，以 2 为底：

log2(n) = log2(2^i)
log2(n) = i
=> i + 1 = log2(n) + 1

但是常数不会影响复杂性=>您有 ~ log 2 (n) steps。

于 2014-10-15T19:45:52.360 回答
0

日志在算法复杂性中出现很多，尤其是在递归算法中。

让我们以二进制搜索为例。

您有一个包含 100 个元素的排序数组 A，并且您正在寻找数字 15..

在二分搜索中，您将查看中间元素 (50) 并将其与 15 进行比较。如果元素大于 15，那么您会找到介于 50 和 100 之间的中间元素，即 75.. 并再次比较.. 如果 15 是大于 75 处的元素，然后查看 75 到 100 之间的元素，即元素 87...您继续执行此操作，直到找到该元素或直到没有更多中间数字...

每次您执行这种检查中间数字的方法时，您都会将剩余要搜索的元素总数减半。.

所以第一遍会给你 O(n/2) 复杂度.. 下一遍将是 O(n/4)... O(n/8) 等等.. 为了表示这种模式，我们使用日志..

因为我们在算法的每一遍都将要搜索的元素数量减少了一半，成为对数基础，所以二进制搜索将产生 O(log2(n)) 复杂度

大多数算法都试图通过将原始数据分解为单独的部分来解决，从而将操作数量“减少”到尽可能少，这就是日志如此频繁出现的原因

于 2014-10-15T19:51:44.250 回答