在C中的O（N）中搜索T

Question

如何遍歷C中O（n）時間的trie樹我想要做一個for循環循環，如果一個字母是匹配，然後搜索該鏈表，但會給我n^2次。有什麼方法可以加快速度？

謝謝！

Answer 1

什麼是在「O（n）」中使用的「n」？如果n表示搜索字符串中的字符數，則可以在O（n）時間內執行以下代碼。 for循環的

/* structure of Trie node */ 
struct trieNode { 
    char *value; 
    childNode children(); 
    int childCount; 
} 

/* structure for childnode in a Trie node. Whichi contains 'key' and pointer to child node */ 
struct childNode { 
    char key; 
    trieNode *node; 
} 


/* setup Trie and search string. (not real code) */ 
trieNode root=createTrinode(...) ; /* Setup Trie of your problem. */ 
char* searchString = inputSearchString(...); /* get string for search */ 

int i; 
trieNode curNode; 

curNode = root; 
for i=0 to len(searchString)-1 
{ 
    curNode = findChildren(curNode,searchString(i)); /* findChildren function returns childnode of first argument, whose key is equal to second argument. (Code of findChildren is omitted) */ 
} 

/* curNode is the traversed leaf node by searchStrin */ 

指數是0到n（searchString的長度）-1，因此該代碼可以執行JN O（n）的時間。

此代碼不考慮serach-string不包含在給定的Trie中的情況。