计数Trie中的节点 -- data-structures 领域 和 trees 领域 和 probability-theory 领域 和 average-case 领域 cs 相关 的问题

Counting nodes in a trie


简体版||繁體版
3
vote

问题

中文

我正在研究随机尝试在我的一个课程中,并想知道是否有人可以提供有关问题的任何指导。

问题: 给定随便$ M $总叶子的True,让$ i $是树中的内部节点的数量(即不是叶子的节点),显示$ e(i)$ $ o(n)$。

关于分布: 我们有一个$ m $ bysty的字母(因此$ m $ m $ m $ clie),每个字母都有相应的概率$ p_i $。我们通过从我们的分发,第二个字母等中绘制第一个字母,随机创建无限长度的$ n $字母。最后,我们将这些$ n $无限单词插入$ k $-$ trie。这个Trie将是无限的,但我们通过删除只有我们的$ N $字的任何一个遍历的路径来修剪它,以消除"冗余" 。

尝试:我尝试将物品与随机特色的大小相关联,我称之为$ s $。 TRIE中的每个非根节点都是某些内部节点的子节点,因此$ MI = S-1 $
那是$ e(i)= e left( frac s m 右) - frac 1 m $
所以,如果我能证明随机特色的预期大小是O(n)我是金色的。但遗憾的是,我们在课堂上所涵盖的一切都涉及给定的Trie的预期深度和高度,我没有任何想法向前发展。谁能在这里提供关于可能有用的建议?

英文原文

I'm studying random tries in one of my classes, and was wondering if anyone could offer any guidance regarding a problem.

Question: Given a random $m$-ary trie with $n$ total leaves, letting $I$ be the number of internal nodes in the tree (that is, nodes which aren't a leaf), show that $E(I)$ is $O(n)$.

About the distribution: We have an alphabet of $m$ letters (hence an $m$-ary trie), each with a corresponding probability $p_i$. We randomly create $n$ words of infinite length by drawing the first letter from our distribution, the second letter, etc. Finally, we insert these $n$ infinite words into a $k$-ary trie. This trie will be infinite in length, but we prune it by removing any paths which are traversed by only one of our $n$ words, to eliminate 'redundancy'.

Attempt: I tried relating things back to the size of the random trie, which I call $S$. Every non-root node in the trie is the child of some internal node, so $mI = S-1$
That is $E(I) = E\left(\frac S m\right) - \frac 1 m$
So if I can show that the expected size of a random trie is O(n) I'm golden. But unfortunately everything we've covered in class relates to expected depths and heights of a given trie, and I don't have any ideas moving forward. Could anyone offer advice on what might be useful here?

           
       
       

回答列表

3
 
vote

如果您的Trie中没有任何学位-1节点(这是树),而不是比内部节点更多的叶子。所以在这种情况下,你有$ i le n $。

取决于你如何定义TRIE,无论您可以拥有许多内部度-1节点。如果学习压缩trie ,则为1个节点的所有路径都会合并到边缘,因此您已完成。对于未压缩的特色,我担心,你可以有许多学位-1节点。假设你有一个字母$ a_i $,非常常见,并且具有1美元的概率为1- varepsilon $和$ varepsilon in oomega(1 / n ^ 2)$。然后,您的Trie包含许多具有高概率的长度-1路径。在这种情况下,您可以拥有超过$ O(n)$内部节点。请自己做计算(如果您喜欢,您可能会选择较小的$ varepsilon $)。

 

If you don't have any degree-1 nodes in your trie (which is a tree) than you have more leaves than interior nodes. So in this case you have $I\le n $.

It depends a bit how you define the trie whether you can have many interior degree-1 nodes. If you study a compressed trie the all the path of degree-1 nodes are merges to an edge, so you are done. For an uncompressed trie, I am afraid, you can have many degree-1 nodes. Say you have one letter $a_i$ that is very common and has a high probability of $1-\varepsilon$ and $\varepsilon\in \Omega(1/n^2)$. Then your trie contains many long degree-1 paths with high probability. In this case the you can have more than $O(n)$ interior nodes. Please do the computations by yourself (you might choose a smaller $\varepsilon$ if you like).

 
 

相关问题

0  将项目附加到数组的平均运行时间是多少?  ( What is the average runtime of appending items to arrays ) 
是一年中的一年中的时间在最终考试中,我正在准备现在我的准备,我在理解将物品附加到阵列的运行时间来看,我在热水中找到自己。 基本上,我知道有不同的方式将物品附加到数组,但请考虑此方法附加方法和它的平均运行时。我已经设法找到了另一个运行时间,但不是它的平均值。 此方法在课堂上将项目介绍给我,并且诀窍是在满满的时候加倍数组...

0  搜索数组的平均时间复杂性[关闭]  ( Average time complexity of searching an array ) 
关闭。这个问题需要详细信息或清晰度。它目前不接受答案。 想要改进这个问题?添加详细信息并阐明编辑此帖的问题。 关闭 6年前。 ...

3  为什么线性搜索平均是$ frac {n} {2} $比较?  ( Why does linear search have fracn2 comparisons on average ) 
我正在阅读线性搜索上的wikipedia页面,提到平均$ frac {n} {2} $比较。 我自己尝试一下自己工作。 首先我被认为是案件的数量。当目标值为1美元的$ 1,$ 2 $ nd,...,$ n $ th列表时,有$ N $案例。还有一个条目根本不在列表中的情况,所以我们有$ n + 1 $案例。 接下来...

4  输入数据概率生成模型下NP-Hard优化问题的近似值或解的概率硬度  ( Probabilistic hardness of approximation or solution of np hard optimization prob ) 
如此,在生物学(DNA序列)中,序列对准是最长常见的通用,其中两个序列的对准通常具有线性函数,每个序列将有多少空间和每个可能的一对对齐字符显示在对齐中。就像最长的常见子序列一样,在使用动态编程的二次时间中,在任意线性评分方案下找到两个字符串的最佳对准。 (Constleman-Wunsch算法)。使用线性评分方案和询...

1  系列的渐近生长  ( Asymptotic growth of a series ) 
我们如何证明: $$ sum_ {k = 1} ^ {c log n-1} :k cdot left( frac {1} {2} 右)^ { frac {k} {3}} 在o o 左(1 右) quad mbox {?} $$ ...

2  查找可快速包含特定元素的$ k $子集  ( Find k subsets containing a particular element quickly ) 
假设$ U $的$ N $子集。我想快速(在平均案例方面)找到包含$ e in u $的k $(< n)$(呼叫这个提取(e))。元素是整数。 到此效果,我想预处理/编码$ N $子集,以便这种提取操作可​​能相对快速地发生,而不管y $ is(假设此项目均匀地选择查询)。 我没有良好的直觉,以便各种方法做到...

2  如何完成工作的平均案例运行时间(和其他算法)?  ( How to go about working the average case run time of this trivial algorithm and ) 
这是一个类似的算法到一个我在上一个问题中使用的算法,但我试图在这里说明一个不同的问题。 for (int i = 0; i < numbers.length - 1; i++) { for (int j = i + 1; j < numbers.length; j++) { if (num...

5  证明二进制搜索的平均案例复杂性是O(log n)  ( Proving that the average case complexity of binary search is olog n ) 
我知道二进制搜索的平均和最坏情况复杂性是O(log n),我知道如何使用复制关系证明最坏的情况复杂性是O(log n)。 但是,我如何证明二进制搜索的平均案例复杂性是o(log n)? ...

2  平均案例分析帮助  ( Average case analysis help ) 
我暂时试图了解如何解决以下问题。有人可以请向初学者解释平均病例分析吗? 考虑以下算法a,它用作输入比特串b = b_1,b_2,...,b_n(每个b_i为0或1),并执行以下操作: A(b,n) k = 0 FOR i = 1 TO n DO IF b_i = 1 THEN k = k ...

0  Quicksort的平均案例运行时间分析很好参考  ( Good reference for average case runtime analysis of quicksort ) 
我是编程中的初级知识,知识技术知识。我被分配到Quicksort的平均案例分析中进行"阅读项目" 。我的意思是我必须在课堂上呈现它。现在,我需要一个很好的来源,我可以阅读它并找到我可以在演示中包含的材料。至于我对算法的现有知识,人们可以假设我几乎不知道,除了"只是代码" ,什么都没有任何关于他们的分析。任何具有严格证...

15  Knuth,De Bruijn和Rice(1972)的“种植平面树的平均高度”  ( On the average height of planted plane trees by knuth de bruijn and rice 197 ) 
我正在尝试派生只有基本手段的标题(没有生成函数,没有复杂的分析,没有傅立叶分析,虽然具有更低的精度。简而言之,我希望证明具有$ N $节点的平均身高$ H_N $(即,从根到叶子的最大节点数)满足$ h_n sim sqrt { pi n} $。 轮廓如下。让$ a_ {nh} $是高度小于或等于$ h $的树的...

1  一种简单的最大发现算法的平均分析  ( Average case analysis of a simple max finding algorithm ) 
给出了这段代码: Valid combinations: 1 2 (1 - 2 connection) 2 3 (2 - 3 connection) 3 1 (3 - 1 connection) 1 2, 2 3 (1 - 3 connection) 1 2, 3 1 (2 - 3 connect...

6  这种可恶劣算法的时间复杂程度是多少?  ( What is the time complexity of this atrocious algorithm ) 
这一探讨了故意糟糕的算法;信用到 benneh 在XKCD论坛上的伪代理算法,我'转换为python,所以你可以实际运行它: def sort(list): if len(list) < 2: return list else: if list[0] <= mini...

3  在通用布尔公式中找到真实或错误分配的硬度?  ( Hardness of finding a true or a false assignment into a generic boolean formula ) 
我读过一些研究,分析了平均案例中SAT解决的硬度。 实际上,对于3CNF公式,如果将子句与变量的比率计算为变量的比率,则存在求解公式的间隔(或多或少为4和5)。但它很容易(在0到4之间)比率5的满足分配的高概率和不可挑离的分配的高可能性。 我的问题是,概述了不正常形式的通用公式。我们可以对其硬度说些什么? ...

0  找到最大算法的平均时间复杂度  ( Finding the average time complexity for a max algorithm ) 
我试图找到最大值的平均例外情况在下面的算法 99887665544330 。 find_max(L): max = -oo # negative infinity for k = 0 to len(L)-1: if L[k] > max: ma...

4  用于执行插入的单个链接列表的平均时间复杂性是多少?  ( What is the average time complexity for a single linked list for performing an ) 
我认为这将是一个非常简单的 O(n) B.C.您可以在列表中使用任何内插入。 列表越长,平​​均越长,才能完成插入。 但是,根据 bigocheatsheet 它是 O(1) 或没有依赖于大小列表。 这里有什么问题? ...

2  问题发现PESIN MAX算法的平均案例  ( Trouble finding average case of a find max algorithm ) 
我正在尝试找到最大的平均速度由下面包含的算法查找。 findMax(list): maxNum = -oo # negative infinity for k = 0 to len(list)-1: if list[k] > maxNum: maxNum=...

2  循环的时间复杂性  ( Time complexity of this while loop ) 
所以,我想知道以下代码的时间复杂性: x = (float) rand() / rand(); // T(4) while (x >= 0.01) // T(?) { x *= 0.8; // T(?) x T(2) } 假设所有基本操作都是完善的一次,是最好的情况t(1) - 恒定的时...

14  泡沫排序中的掉次数  ( Expected number of swaps in bubble sort ) 
给定数组$ $ n $整数,数组中的每个元素都可以通过一些概率$ p [i] $,$ 0 leq i&lt; n $。我必须找到将使用泡泡排序对阵列进行排序。 我已经尝试了以下内容: 元素$ a [i]&gt的概率; a [j] $ i&lt;可以从给定的概率轻松计算J $。 使用上面的,我已经计算了次数的...

1  您如何表达关于不成功搜索的定理声明平均 - 与量子散列中的不成功搜索?  ( How do you express the theorem statement about unsuccessful search on average ca ) 
我正在阅读CLRS和定理11.1它状态: 在其中通过链接解析冲突的哈希表中,在简单统一散列。 我试图了解如何用量词表达这个定理($ 存在, forall $)以及它如何与"平均案例" 时间(精确,它们的平均案例时间)。 是定理是所有或任何关键的声明?或者它是平均所有关键的关键,并且"平均" 是什么意思,严格呢? ...

11  评估给定的Bubblesort算法的平均时间复杂度。  ( Evaluating the average time complexity of a given bubblesort algorithm ) 
考虑到Bubblesort的伪代码: FOR i := 0 TO arraylength(list) STEP 1 switched := false FOR j := 0 TO arraylength(list)-(i+1) STEP 1 IF list[j] > list[...

1  鉴于算法,其运行时案例的概率是什么?  ( Given an algorithm what are the probabilities for its run time cases ) 
我被赋予此算法 ,我也给出了$ 1 leq k leq n $。 如果我们让x是执行第2行的次数,那么我应该找到不同案例的运行时概率。 因此我知道最好的情况是[n-1] = k $,因为第2行只会被调用一次。 我知道$ k 1,2,...... n $。 和施工$ a [n-1] 在0,1,2,... n...

3  预期成本和算法平均成本之间有什么区别?  ( What is the difference between expected cost and average cost of an algorithm ) 
在经历概率/平均分析算法时,我发现在平均成本和预期成本的某个地方写入。有人可以告诉我完全预期的成本代价是什么。我认为我们照顾了活动的可能性,同时找到与平均成本不同的预期成本。 ...

7  在流中保持k $最小的整数的复杂性  ( Complexity of keeping track of k smallest integers in a stream ) 
我需要分析在线算法的时间复杂性,以跟踪从$ $ numb的流中追踪最低$ k $号码。该算法是 假设流中的$ i $ th号码是$ s_i $。 保持尺寸的最大堆$ k $。 如果堆包含少于$ k $元素,请为堆添加$ s_i $。 否则:如果$ s_i $小于堆中的最大元素(即堆的根),请用$ s_i $替换堆的...

6  二进制搜索树和AVL树的平均深度  ( Average depth of a binary search tree and avl tree ) 
我的教授最近提到二进制搜索树中的节点的平均深度将是$ o(log(n))$ why $ n $是树中的节点量。我最终绘制了一堆二进制搜索树,我不认为我是正确了解这个概念。例如,如果$ n = 4 $ the tree,则将具有最大3美元或节点的最大深度的节点,最大深度为2美元。在最大值为3美元的情况下,我们将有0美元...

相关问题

0  将项目附加到数组的平均运行时间是多少? 
0  搜索数组的平均时间复杂性[关闭] 
3  为什么线性搜索平均是$ frac {n} {2} $比较? 
4  输入数据概率生成模型下NP-Hard优化问题的近似值或解的概率硬度 
1  系列的渐近生长 
2  查找可快速包含特定元素的$ k $子集 
2  如何完成工作的平均案例运行时间(和其他算法)? 
5  证明二进制搜索的平均案例复杂性是O(log n) 
2  平均案例分析帮助 
0  Quicksort的平均案例运行时间分析很好参考 
15  Knuth,De Bruijn和Rice(1972)的“种植平面树的平均高度” 
1  一种简单的最大发现算法的平均分析 
6  这种可恶劣算法的时间复杂程度是多少? 
3  在通用布尔公式中找到真实或错误分配的硬度? 
0  找到最大算法的平均时间复杂度 
4  用于执行插入的单个链接列表的平均时间复杂性是多少? 
2  问题发现PESIN MAX算法的平均案例 
2  循环的时间复杂性 
14  泡沫排序中的掉次数 
1  您如何表达关于不成功搜索的定理声明平均 - 与量子散列中的不成功搜索? 
11  评估给定的Bubblesort算法的平均时间复杂度。 
1  鉴于算法,其运行时案例的概率是什么? 
3  预期成本和算法平均成本之间有什么区别? 
7  在流中保持k $最小的整数的复杂性 
6  二进制搜索树和AVL树的平均深度 



© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有