最近很多小伙伴都在问解释这种针对Cat/Egg投掷问题的O和nlogn算法这两个问题，那么本篇文章就来给大家详细解答一下，同时本文还将给你拓展log（n！）=Θ（n·log（n））吗？、nlogn是O

最近很多小伙伴都在问解释这种针对Cat / Egg投掷问题的O和n log n算法这两个问题，那么本篇文章就来给大家详细解答一下，同时本文还将给你拓展log（n！）=Θ（n·log（n））吗？、n log n是O（n）吗？、O（log n）算法在排序数组中找到最佳插入位置、O（n log log n）时间复杂度等相关知识，下面开始了哦！

本文目录一览：

• 解释这种针对Cat / Egg投掷问题的O（n log n）算法
• log（n！）=Θ（n·log（n））吗？
• n log n是O（n）吗？
• O（log n）算法在排序数组中找到最佳插入位置
• O（n log log n）时间复杂度

解释这种针对Cat / Egg投掷问题的O（n log n）算法

这个问题（您需要从建筑物中扔出多少只猫才能确定这种猫可以生存的最大楼层。实际上相当残酷）对于O（n ^
3）的复杂度已经得到了公认的答案。该问题等效于此Google Code
Jam，对于N =
2000000000而言应该可以解决。

似乎O（n ^
3）解决方案不足以解决它。从解决方案页面中查找，jdmetz的解决方案（＃2）似乎是O（n
log n）。我不太了解该算法。有人可以解释吗？

编辑

答案1

小编典典

最高的解决方案实际上是O(D*B)（使用问题的术语），但是作者注意到，对于大多数人来说D，B答案将大于2^32并且-1可以返回。
所以，他介绍maxn等于1100 -最大D和F为它是有道理的计数。
因为D, B = 10000他马上返回-1。对于D, B = 100递归公式，使用下面的公式。仅对某些“角值”（例如D = 10000, B =2）使用直接公式。（有关“直接公式”的详细信息，请参阅他的评论）

为此D, B < maxn，作者在评论中提供了公式：f(d,b) = f(d-1,b)+f(d-1,b-1)+1。f这里的函数返回最多可以使用“
d尝试”和“ b鸡蛋”来确定“断点”的楼层数。
公式本身应该是不言而喻的：无论我们在哪个楼层投出第一枚鸡蛋，都有两个结果。它可能会破裂，然后我们可以检查f(d-1,b-1)下面的楼层。或者它可以“生存”，那么我们可以检查f(d-1,b)上面的楼层。以当前楼层为单位，这使其f(d-1,b)+f(d-1,b-1)+1总数为零。

现在，可以轻松地将其编码为DP（动态编程）。如果您留下无穷大（2^32）签出，它将变得非常干净。

    for (int i = 1; i < maxn; ++i) {        for (int j = 1; j < maxn; ++j) {            f[i][j] = f[i - 1][j - 1] + f[i - 1][j] + 1;        }    }

当我们有f[D][B]存储这些结果的数组时，找到D''和B''是二进制搜索。（因为函数f由d和都单调增长b）

PS尽管我在回答“猫”问题时确实说过，有一个更快的解决方案，但实际上比我想的要 酷 ：)多亏了您和 sclo （作者）！

log（n！）=Θ（n·log（n））吗？

我要证明 log（ n ！）=Θ（ n ·log（ n ））。

提示我应该用 n n 表示上限，而用 （ n / 2）（ n /
2）表示下限。在我看来，这似乎并不那么直观。为什么会这样呢？我绝对可以看到如何将 n n 转换为 n ·log（ n
）（即，记录方程的两边），但这有点倒退。

解决这个问题的正确方法是什么？我应该画递归树吗？对此没有任何递归，因此这似乎不是一种可行的方法。

答案1

小编典典

请记住

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)

您可以通过以下方式获得上限

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)                                = n*log(n)

在丢弃总和的前一半之后，您可以通过执行类似的操作来获得下界：

log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n)                                        = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)                                       >= log(n/2) + ... + log(n/2)                                        = n/2 * log(n/2)

n log n是O（n）吗？

O（log n）算法在排序数组中找到最佳插入位置

我正在尝试寻找一种找到最佳位置的算法，以将 目标 插入已排序的数组中。

目标是要么返回该项目在列表中的位置，要么返回将其保持列表排序的位置。

所以说我有一个清单：

   0   1   2   3   4    5    6 --------------------------------- | 1 | 2 | 4 | 9 | 10 | 39 | 100 | ---------------------------------

我的目标项目是14 它应该返回一个索引位置5

我目前拥有的伪代码：

array = generateSomeArrayOfOrderedNumbers()number findBestIndex(target, start, end)    mid = abs(end - start) / 2    if (mid < 2)         // Not really sure what to put here        return start + 1 // ??    if (target < array[mid])        // The target belongs on the left side of our list //        return findBestIndex(target, start, mid - 1)    else        // The target belongs on the right side of our list //        return findBestIndex(target, mid + 1, end)

我不太确定现在要写些什么。我试图对此采取二进制搜索方法，但这是在5次重写左右之后我能想到的最好方法。

答案1

小编典典

您的代码有几个问题：

mid = abs(end - start) / 2

这是 不是 之间的中间start和end，这是他们之间的距离的一半（四舍五入到整数）。后来，您将其用作确实是有效的索引：

findBestIndex(target, start, mid - 1)

不是。您可能打算在mid = (start + end) // 2这里使用或其他东西。您还会错过一些索引，因为您跳过了中间部分：

return findBestIndex(target, start, mid - 1) ...return findBestIndex(target, mid + 1, end)

现在，您的基本情况也必须有所不同。一个好的候选人是条件

if start == end

因为现在您肯定知道您已经完成搜索。请注意，您还应该考虑所有数组元素都小于的情况target，因此您需要在最后插入它。

我不经常搜索二进制文件，但是如果我这样做，这就是

如果您从未尝试过二进制搜索，那么很难正确地进行二进制搜索。如果执行二进制搜索，通常会使用以下模式：

lo, hi = 0, n // [lo, hi] is the search range, but hi will never be inspected.while lo < hi:    mid = (lo + hi) // 2    if check(mid): hi = mid    else:          lo = mid + 1

在该条件check是一个单调二元谓词（它始终是false直到某个点和true从该点），该循环后，lo ==hi将在范围内的第一个数字[0..n]与check(lo) == true。check(n)隐式地假定它是正确的（这是此方法的魔力的一部分）。

那么，true对于包括我们目标false位置前后的所有索引以及之前目标位置的所有索引而言，单调谓词是什么？

如果我们考虑一下，我们想在数组中找到比目标大的第一个数字，因此我们只需要插入它就可以了：

lo, hi = 0, nwhile lo < hi:    mid = (lo + hi) // 2    if (a[mid] > target): hi = mid    else:                 lo = mid + 1return lo;

O（n log log n）时间复杂度

我在这里有一个简短的程序：

Given any n:i = 0;while (i < n) {   k = 2;   while (k < n) {        sum += a[j] * b[k]        k = k * k;   }   i++;}

它的渐近运行时间为O（n log log n）。为什么会这样呢？我知道整个程序至少要运行n次。但是我不确定如何找到日志log n。内部循环取决于k *k，因此显然要小于n。如果每次是k / 2，那将只是n log n。但是您如何确定答案是log log n？

答案1

小编典典

为了进行数学证明，内循环可以写为：

T(n) = T(sqrt(n)) + 1w.l.o.g assume 2 ^ 2 ^ (t-1)<= n <= 2 ^ (2 ^ t)=>we know  2^2^t = 2^2^(t-1) * 2^2^(t-1)T(2^2^t) = T(2^2^(t-1)) + 1=T(2^2^(t-2)) + 2 =....= T(2^2^0) + t =>T(2^2^(t-1)) <= T(n) <= T(2^2^t) = T(2^2^0) + log log 2^2^t = O(1) + loglogn==> O(1) + (loglogn) - 1 <= T(n) <= O(1) + loglog(n) => T(n) = Teta(loglogn).

然后总时间为O（n loglogn）。

为什么内循环是T（n）= T（sqrt（n））+1？ 首先查看内部循环何时中断，当k>
n时，意味着k至少在sqrt（n）之前，或者在k等于最大sqrt（n）之前处于两个级别，因此运行时间为T（sqrt（n））。 +
2≥T（n）≥T（sqrt（n））+ 1。

今天的关于解释这种针对Cat / Egg投掷问题的O和n log n算法的分享已经结束，谢谢您的关注，如果想了解更多关于log（n！）=Θ（n·log（n））吗？、n log n是O（n）吗？、O（log n）算法在排序数组中找到最佳插入位置、O（n log log n）时间复杂度的相关知识，请在本站进行查询。

本文标签：

• O(n_log_n)算法
• Cat_Egg投掷问题
• 时间复杂度优化
• 编程解决方案