时间戳

首页 > 解决方案 > 求解while循环时间复杂度算法

algorithm - 求解while循环时间复杂度算法

问题描述

我很难弄清楚我的算法的时间复杂度。我知道算法的“for”部分将在 O(n) 中运行，但我不确定我的 while 循环。该问题涉及从给定向量创建二叉树。每个节点都根据其值及其在向量中的索引进行评估，因此，基本上，每个后续节点都必须位于前一个节点的右侧，并且根据其值是更大还是更小，它将是子节点或父节点。父节点的子节点的值必须更小。

在子节点小于要放置的下一个节点的情况下，我使用了 while 循环，并且我跟踪父节点，直到找到要放置新节点的位置。我相信这会在最坏的情况下运行 k-1 次，k 是树的深度，但是我如何将其表示为时间复杂度？O(kn)? 那是线性的吗？ 

for(int i = 0; i < vecteur_source.size(); i++){
    if( i == 0){
        do bla....
    }else if((vecteur_source.at(i) > vecteur_source.at(i-1)) && (m_map_index_noeud.at(i-1)->parent)){
        int v = m_map_index_noeud.at(i-1)->parent->index;
        while ((vecteur_source.at(i) >= vecteur_source.at(v))){
            v = m_map_index_noeud.at(v)->parent->index;
        }
    }
}

标签： algorithmtime-complexity

解决方案

请允许我将其简化为伪代码：

# I'm assuming this takes constant or linear time
do the thing for i = 0

for i ← 1 to n-1:
    if source[i] > source[i-1] and nodes[i] is not the root node:
        v ← nodes[i-1].parent.index
        while source[i] > source[v]:
            v ← nodes[v].parent.index

如果我从您的代码中正确理解了它，那么您的分析是正确的：外部循环迭代 O( n ) 次，内部循环迭代最多 O( h ) 次，其中h是树的高度，因此时间复杂度为 O( nh )。

这不是线性时间，除非h被保证最多是一个常数。更常见的是，平衡树的h为 O(log n )，不平衡树的最坏情况为 O( n )。

推荐阅读