Блог пользователя Nguyen_Khac_Trung

What is the complexity of st.erase(st.begin())?
Автор Nguyen_Khac_Trung, история, 12 месяцев назад, По-английски

What is the complexity of st.erase(st.begin())?

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
12 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

It should be O(logn)

→ Ответить
  • »
    »
    12 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится 
    for(r=0;r<b.size();r++) tmp+=a[r];
if (tmp==b) res.pb(1);
while (r<a.size())
    {
        tmp.erase(tmp.begin());
        tmp+=a[r++];l++;
        if (tmp==b) res.pb(l+1);
    }

    so this code will has O(NlogN), right? :>

    → Ответить
»
12 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What st is? What cppreference tell about it?

→ Ответить
»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For a set, the complexity would be O(logn)

→ Ответить
»
12 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Is st a set? If so, then it's O(log n), but it seems like your st is a string, in which case it's O(n).

→ Ответить