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 侧(右子树)重复相同的操作。对所有特征重复。

我们知道完美二叉树的 big-Omega(最坏情况)是 log(n) [base 2]。所以 log(255) [base 2] 大约是 8，而且这一定是所需的最大步数。