我正在编写一种算法,该算法首先采用各种端点的配置文件及其关联方法,如下所示:
/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
, if guest
在这里,客人将有一个wildcard
节点,所以如果abc
与任何一个都不匹配guest
的节点,但有一个wildcard
节点存在它将转到wildcard
。然后它会看起来wildcard
看看它是否有friends
节点,如果有的话就去那里。那么如果friends
是叶子节点就会返回相应的方法。
这个算法有意义吗?我想知道查找的运行时间是多少。我认为这将是 O(n),其中 n 是传入参数中的标记数量。
Here is an image of the graph I would build based on the input above. Each diamond represents an endpoint method.
谢谢你的帮助!
最差查找时间将为 O(E+N),其中 E 是边数,N 是节点数。因为我们不知道每一级有多少个节点。因此,根据您的算法,您可以通过进行级别搜索来找到所需序列中的第一个节点,因为您没有任何参数可以检查是否经过所需的路径。
(我知道每次下降一级时节点数量都会减少,但在这种情况下减少多少是不确定的)
它甚至不是 n 数组。
通配符无助于降低最坏情况的时间复杂度,并且无法确定树的最佳情况。通配符检查需要恒定的时间,并且不计入运行时间。
现在算法看起来有点令人困惑,当你有两个选择时你会做什么
1)你有自然匹配的节点
2)你有通配符节点。
在同一水平线上,你会去哪里?
假设你我们按照你遇到的第一个方向前进。但是,如果这不是您在最后一个节点了解的实际路径,那么您将回溯它,该怎么办?为了避免这种情况,您将通过 BFS 标记每个级别的可用路径数量并进行搜索。
因此,如果您已经处理了所有情况,最坏情况时间复杂度将为 O(E+N)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)