2

我正在编写一个算法，它将首先采用各种端点的配置文件及其相关方法，如下所示：

/guest guestEndpoint
/guest/lists listEndpoint
/guest/friends guestFriendsEndpoint
/guest/X/friends guetFriendsEndpoint
/guest/X/friends/X guestFriendsEndpoint
/X/guest guestEndpoint
/X/lists listEndpoint
/options optionsEndpoint

X这里代表一个通配符，所以任何字符串都可以匹配。该算法会将其作为输入并构建一棵树，其中每个节点代表/'s 之间的一个标记。每个叶子都是一个有效的端点。

然后当用户传入类似guest/abc/friends它会从根开始遍历树的东西时，然后查找guest连接到根的节点，如果存在则转到节点guest，如果guest这里来宾将有一个wildcard节点，那么如果abc不匹配任何ofguest的节点，但存在一个wildcard节点，它将转到wildcard. 然后它会查看wildcard它是否有一个friends节点，如果有就去那里。然后如果friends是叶节点，它将返回相应的方法。

这个算法有意义吗？我想知道查找的运行时间是什么。我认为这将是 O(n) 其中 n 是传入的参数中的令牌数。

这是我将根据上面的输入构建的图表的图像。每个菱形代表一个端点方法。 在此处输入图像描述

谢谢你的帮助！

4

1 回答 1

2

最坏的查找时间将是 O(E+N)，其中 E 是边数，N 是节点数。因为我们不知道每个级别有多少个节点。因此，通过您的算法，您可以通过执行级别搜索找到所需序列中的第一个节点，因为您没有任何参数来检查通过所需路径。（我知道每次下降一级时节点的数量都会减少，但在这种情况下有多少是不确定的）它甚至不是 n 数组。

通配符无助于降低最坏情况的时间复杂度，并且不确定是否知道树的最佳情况。通配符检查需要恒定的时间，并且不会计入运行时间。

现在算法看起来有点混乱当你有两个选择时你会做什么

1）你有自然匹配的节点 2）你有通配符节点。

在同一层，你会去哪里？假设你我们先去你遇到的方向。但是，如果它不是您在最后一个节点知道的实际路径，那么您回溯它怎么办。为避免这种情况，您将通过 BFS 标记每个级别的可用路径数并进行搜索。因此，如果您处理了所有情况，最坏情况的时间复杂度将是 O(E+N)。

于 2017-07-22T19:35:17.647 回答