algorithm - 最坏情况二分查找？

Question

问题是:

In order to distinguish ordinary emails from spam, an algorithm with several features has been designed. Every feature provides information about the message, for instance number of suspicious words, the length of the message, degree of matching with spam templates etc. Every feature is a discrete variable with two values, for example, low/high, short/long, and similar/dissimilar. A tree with 255 nodes has been employed to make the decision whether to reject an email. How many operations/steps/time units are required at most to process each email?

我认为这将是一个完美的二叉树，因此 2^n - 1 = 255，因此 n = 8。但是，我开始考虑以下“最坏情况”场景:

...O
../\
.O..O
..../\
...O..O
and so forth.

这会使用二分搜索递归关系吗？ T(n)=T(n/2)+1？

Answer 1

我认为你的答案是正确的，杰伊。根据问题，我将树画成这样:

>                     o
>                    /\
> feature 1:        o  o
>                  /\  /\
> feature 2:      o  o o o
> 
                   ...

所以你从一个根值开始。然后你询问电子邮件是否已成功满足该特征，因此它分为 2 个节点，Y 或 N。对于 Y(左子树)，你询问电子邮件是否满足第二个特征，Y 或 N，并且这又分成 2 个节点，并且在 N 侧(右子树)上重复相同的操作。对所有功能重复此操作。

我们知道完美二叉树的大欧米茄(最坏情况)是 log(n) [base 2]。因此 log(255) [base 2] 大约为 8，这一定是所需的最大步数。