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

Автор wiaderko69, история, 13 месяцев назад, По-английски

Can someone tell me what's the time complexity of this code? I thought it's O(N^2) because of vector erase but it gets AC 332397335.

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

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

Auto comment: topic has been updated by wiaderko69 (previous revision, new revision, compare).

»
13 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

It's O(N)

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

Your code is indeed $$$\mathcal{O}(n^2)$$$ consider a case where

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

consists of

Unable to parse markup [type=CF_MATHJAX]

ones, next

Unable to parse markup [type=CF_MATHJAX]

twos and finally

Unable to parse markup [type=CF_MATHJAX]

one;

Unable to parse markup [type=CF_MATHJAX]

would be equal to

Unable to parse markup [type=CF_MATHJAX]

.