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

Can't understand time complexity
Автор pranp_24, история, 18 месяцев назад, По-английски

I was just working on a problem and I can't understand why one of my solutions passed and the other didn't.

I have two loops that are the same complexity. Since they are the same complexity, it should simplify to O(N)+O(N)=O(2N) which just becomes O(N). When I take out one of the loops, my solution passes, but when I keep them both in I get TLE. I don't understand this since they should simplify to the same complexity. Can someone please help?

Not accepted solution:

while(number>0){
  if(number % 2==0){
       stack.add(1);
  }
  else{
     stack.add(2);
  }
  number/=2;
}

int originalsize= stack.size();
for (int i = 0; i < originalsize; i++) {
   System.out.print(stack.pop()+ " ");
}

Accepted solution: 

String ans="";
while(number>0){
  if(number % 2==0){
       ans="1 "+ans;
  }
  else{
     ans="2 "+ans;
   }
  number/=2;
}
System.out.println(ans);

Problem link: https://codeforces.net/contest/1810/problem/B

Accepted Solution: https://codeforces.net/contest/1810/submission/207920289

Not accepted Solution: https://codeforces.net/contest/1810/submission/207919439

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

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

Time complexity isnt really precise, so one O(n) can be slower than the other. For example you can imagine that if you do 100 for loops of 2 iterations it would be slower than if you do 1 for loop with 2 iterations, because 100>1. Big o notations are only invented as a relative measure.

You can read more here

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

The stack operations are running in O(n) time. This blog talks about it with the solution just being a linked list.

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

The reason you get TLE is because calling System.out.print is dreadfully slow. You should use PrintWriter instead, see 207955776. The reason you got TLE on one submission and AC on the other is simply because the TLE submission calls System.out.print more times than your AC submission.

... Since they are the same complexity, ...

This is incorrect. Funnily enough, your TLE submission has strictly better time complexity than your AC submission. The reason is that operations like ans="1 "+ans; does not run in constant time. Prepending a character to ans runs in O(len(ans)) time.

Btw, consider avoiding using Stack in Java. It is an old relic from the past. Use ArrayList or ArrayDeque instead, for example see 207955498.

→ Ответить