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

Problem with time !!!
Автор eGoMask, история, 3 года назад, По-английски

why my this code 118446438 get Time limit exceeded and this code 118446206 get accepted in problem 1535C - Unstable String

any hint

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

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

for(int i=0 ; i<strlen(s) ; i++)

strlen(s) has $$$O(n)$$$ complexity so this whole loop has $$$O(n^2)$$$ complexity.

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

strlen() is O(n)

the way strlen works is that it will scan and count, until it finds a null character: every time you call strlen, it scans again and again from the beginning, so it's inefficient, while s.size() is constant

→ Ответить