我的算法的运行时间是多少? [英] What is the runtime of my algorithm?

问题描述

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

I'm writing an algorithm that will first take a config file of various endpoints and their associated method like the following:

/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此处表示通配符，因此任何字符串都将与此匹配. 该算法将以此为输入并构建一棵树，其中每个节点代表/之间的一个令牌.每片叶子都是一个有效的端点.

X here represents a wildcard, so any string would match with this. The algorithm would take this as input and build a tree with each node representing one token between the /'s. Each leaf would be a valid endpoint.

然后，当用户传递类似guest/abc/friends的内容时，它将从根开始遍历树，然后查找附加到根的guest节点，如果存在，则转到节点guest，如果这里的guest将有一个wildcard节点，因此，如果abc与任何guest的节点都不匹配，但是存在一个wildcard节点，它将进入wildcard.然后，它将从wildcard看是否有一个friends节点，如果有的话，去那里.然后，如果friends是叶节点，它将返回相应的方法.

Then when the user passes in something like guest/abc/friends it would traverse the tree starting from the root, then look for a guest node attached to the root, if it exists go to node guest, if guest here guest would have a wildcard node, so if abc did not match with any of guest's nodes but there was a wildcard node present it would go to the wildcard. Then it would look from wildcard to see if it had a friends node, if so go there. Then if friendsis a leaf node it would return the corresponding method.

此算法有意义吗?我想知道查询的运行时间是什么.我想这将是O(n)，其中n是传入的参数中令牌的数量.

Does this algorithm makes sense? I'm wondering what the runtime of the lookup would be. I'm thinking it would be O(n) where n is the number of tokens in the param that was passed in.

这是我根据上面的输入构建的图的图像.每个菱形代表一个端点方法.

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数组.

Worst look up time will be O(E+N) where E is number if edges and N is number of nodes. Becuase We don't know how many nodes are there at each level. So by your algorithm you find first node in desired sequence by doing level search as you don't have any parameter to check for to going through desired path. (I know number of nodes are going to reduce each time I go down by one level but by how many is uncertain in this case) It's Not even n-array.

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

Wild card won't help in reducing time complexity of worst case and will be uncertain to know the best case of a tree. Wild card checking takes constant time and it won't count in run time.

现在的算法看起来有点令人困惑，当您有两个选择时，您会做什么

Now algorithm looks bit confusing what will you do when you have two options

1)您具有自然匹配的节点 2)您具有通配符节点.

1) you have natural matched node 2) you have wild card node.

在同一级别，您将去哪里? 假设您首先遇到的是我们的发展方向.但是，如果这不是您在最后一个节点上知道的实际路径，那么您可以回溯该路径.为避免这种情况，您将使用BFS在每个级别上标记可用路径的数量并进行搜索. 因此，如果您处理完所有情况，最坏情况的时间复杂度将为O(E + N).

On same level , where you will go? Assume you we go in direction first you encountered. But what if It is not the actual path you get to know at last node so you backtrack it . To avoid that you will keep mark of number of available paths at each level by BFS and do the search. So Worst Case time complexity would be O(E+N) provided you have handled all the cases.

这篇关于我的算法的运行时间是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！