Решение алгоритма сложности времени цикла - PullRequest
Новая
       18

Решение алгоритма сложности времени цикла

0 голосов
/ 02 декабря 2019

Мне трудно понять сложность моего алгоритма во времени. Я знаю, что часть «for» алгоритма будет работать в O (n), но я не уверен в своем цикле while. Проблема заключается в создании двоичного дерева из заданного вектора. Каждый узел оценивается по его значению и индексу в векторе, поэтому, по сути, каждый следующий узел должен быть справа от предыдущего, и в зависимости от того, является ли его значение большим или меньшим, это будет дочерний узел или родительский узел. Дочерние элементы родительских узлов должны быть меньше по значению.

Я использовал цикл while для случая, когда дочерний узел меньше, чем следующий узел, который нужно разместить, и я буду следить за родителями до тех пор, поканайти место для размещения нового узла. Я полагаю, что в худшем случае, k-1 раз, k будет глубиной дерева, но как бы это представить как временную сложность? O (кН)? Это линейно? 

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;
        }
    }
}
...