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

Time Complexity of '+' with strings Giving TLE??
Автор Focus_2000, история, 3 года назад, По-английски

Problem: A. Cut and Paste when i am using

s=s+t; [this is giving me TLE on 37 test ] [128332169](https://mirror.codeforces.com/contest/1280/submission/128332169)

and s+=t; is Accepted 128332405 20 ms

can anyone tell me why such happen.???

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

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

s = s + t; this line will create new string object with value s + t and assign it to s, complexity $$$O(|s| + |t|)$$$

s += t; this line just simply append t to s, complexity $$$O(|t|)$$$

#include <bits/stdc++.h>
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    string s = "";

    time_t start = clock();
    for(int i = 0; i < 1000; i++) s = s + "a";
    cout << clock() - start << '\n';

    start = clock();
    for(int i = 0; i < 1000; i++) s += "a";
    cout << clock() - start;
}

This code produced the following output on my system

100
4

So avoid using assignment operator!

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

    Thanks. Found where i am wrong.

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

    When I'm running your code on Dev C++ it is printing 0 0, but in the online C++ compiler, it is giving the right answer. Can you please tell me what is wrong with the Dev C++ compiler? Thank You:)

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

      I guess CLOCKS_PER_SEC on your system has the value 1000. So just add consuming stuff between 2 clock() call, you'll see the difference:

      time_t start = clock();
BogoSort();
cout << clock() - start;

      For better precision, I suggest using chrono. IMO using clock() is better as it's really easy to remember the syntax.

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

I think the '+' operator's complexity is O(2*(n1 + n2)), where n1 and n2 are the lengths of the strings s and t.
The complexity of the operator '+=' might only be O(2*n2) in some implementations on the other hand as only the append() operation is to be performed.
A Stack Overflow Thread
If there is a huge difference between the lengths of s and t, this could effectively work out as the difference between an O(N) algorithm and an O(1) algorithm, and could possibly lead to TLE.

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

Click

→ Ответить