三元搜索的平均情况复杂度

我需要解决三元搜索的平均情况复杂度。在最坏的情况下，你会做两个比较，所以我假定最坏情况的复杂性是这样的：三元搜索的平均情况复杂度

C(n) = C(n/3) + 2

然后可以证明是O（LOGN），但是你会在平均情况是什么样子？我想可能是这样的：

C(n) = C(n/3) + 1.5

因为您平均可能做1〜2比较，以便（1 + 2）/ 3 = 1.5

来源

2013-10-07 dood

不是三元搜索*总是*每次迭代执行两次查找？ – templatetypedef

@templatetypedef你为什么需要？如果（e <数据[n/3]）看起来还有其他的话，如果（e <数据[2n/3]）看起来中间还有其他的看起来是正确的（好吧，稍微复杂一点考虑平等，但是相同数量的比较）。 – Dukeling

我觉得你在三元搜索中混淆了三元搜索TREE。你的问题和澄清对于一棵树来说是有意义的，但对于一般的三元搜索来说并不合适。 –

如果我们都在谈论搜索的元素被排序的阵列，我认为平均来说你必须做5/3的比较。假设您首先检查要找到的元素x是高于还是低于放置在A（n/3）中的元素，其中A是您的排序数组，n是其长度。统计上，由于1/3的元素低于A（n/3），2/3高，因此x有1/3的机会降低，2/3的机会更高。如果x较低，则不需要进行第二次比较，所以您只需要1. x越高，您需要将其与A（2n/3）进行比较，因此您需要2. 所以平均来说，你需要（1/3）* 1 +（2/3）* 2 = 5/3。

但是，这并没有改变任何东西的全球复杂性，这将永远是O（log n）。唯一的区别将是恒定的因素。

来源

2013-10-07 07:13:12 Traklon

三元搜索的平均情况复杂度

回答

相关问题