我正在编写一种算法，该算法首先采用各种端点的配置文件及其关联方法，如下所示:
/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 这里代表一个通配符，所以任何字符串都会与它匹配。
该算法将以此作为输入并构建一棵树，其中每个节点代表 / 之间的一个标记。每个叶子都是一个有效的端点。
然后，当用户传入诸如 guest/abc/friends 之类的内容时，它会从根开始遍历树，然后查找附加到根的 guest 节点，如果存在则转到节点guest，如果guest这里guest会有一个wildcard节点，所以如果abc与任何 guest 节点都不匹配，但存在一个 wildcard 节点，它将转到 wildcard。然后它会从 wildcard 中查找是否有 friends 节点，如果有，则转到那里。那么如果friends是叶子节点，它将返回相应的方法。
这个算法有意义吗？我想知道查找的运行时间是多少。我认为这将是 O(n)，其中 n 是传入参数中的标记数量。
这是我根据上面的输入构建的图表的图像。每个菱形代表一种终点方法。
感谢您的帮助!
最佳答案
最差查找时间将为 O(E+N)，其中 E 是边数，N 是节点数。因为我们不知道每一级有多少个节点。因此，根据您的算法，您可以通过进行级别搜索来找到所需序列中的第一个节点，因为您没有任何参数可以检查是否经过所需的路径。 (我知道每次下降一级时节点数量都会减少，但在这种情况下减少多少是不确定的) 它甚至不是 n 数组。
通配符无助于降低最坏情况的时间复杂度，并且无法确定树的最佳情况。通配符检查需要恒定的时间，并且不计入运行时间。
现在算法看起来有点令人困惑，当你有两个选择时你会做什么
1) 你有自然匹配的节点 2)你有通配符节点。
在同一层，你会去哪里？ 假设你我们按照你遇到的第一个方向前进。但是，如果这不是您在最后一个节点了解的实际路径，因此您回溯它，该怎么办？为了避免这种情况，您将通过 BFS 标记每个级别的可用路径数量并进行搜索。 因此，如果您已经处理了所有情况，最坏情况时间复杂度将为 O(E+N)。
关于algorithm - 我的算法的运行时间是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45258067/