Большая проблема расчета сложности времени - PullRequest
Новая
       16

Большая проблема расчета сложности времени

0 голосов
/ 11 октября 2019

У меня есть алгоритм и мне нужно рассчитать его временную сложность. По сути, алгоритм выполняет следующие действия: он удаляет все числа, которые встречаются более чем один раз в Stack<int>: 

public static bool Contains(Stack<int> st, int n)
{
    if (st.Count == 0) return false;
    if (st.Peek() == n) return true;


    bool b = false;

    int top = st.Pop();
    if (st.Count > 0)
        b = Contains(st, n);
    st.Push(top);

    return b;
}

public static void TrimDoubles(Stack<int> st)
{
    Stack<int> tmpSt = new Stack<int>();
    Stack<int> banned = new Stack<int>();

    while (st.Count > 0)
    {
        int top = st.Pop();
        if (!Contains(st, top))
        {
            if (!Contains(banned, top))
                tmpSt.Push(top);
        }
        else
            banned.Push(top);
    }

    while (tmpSt.Count > 0)
        st.Push(tmpSt.Pop());
}

. Это то, что я до сих пор имею: временная сложность метода Contains равна O (n) и последняя часть метода TrimExcess. Таким образом, общая временная сложность TrimExcess составляет: 2 + n + 1 + n (1 + 1 + O (n) + O (n) + 1) + O (n) , что соответствует 3 + 4n + n * 2O (n) + O (n)

Это правда? Если это так, значит ли это, что сложность по времени составляет O (n ^ 2) , поскольку n * O (n) = O (n ^ 2) ?

...