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

Is this Code Ok to get saved from TLE and What will be the time Complexity of this???
Автор bideshbanerjee444, история, 3 года назад, По-английски

for(int i = 2; i <= int(1e6); i++){
for(int j = 0; j <= int(1e6); j += i){

//Here anything which takes O(1) time.....

} }

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

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

Complexity is O(nlogn), so it will pass.
Also, you can use custom invocation to check run time.

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

    wrong is O(1)

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

      Notice that j += i. So the overall complexity is $$$O(\frac{n}{1} + \frac{n}{2} + \dots + \frac{n}{n}) = O(n \log n)$$$

      I dont think computer are smart enough to solve that kind of loop.

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

        but n is constant (1e6)

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

          So?

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

          It is more complex then you think just a $$$O(1)$$$ and compiler can predict all 2-loops.

          Some problem are even already hard to make $$$O(n \log n) \rightarrow O(n \log \log n)$$$ even if the inside function run in $$$O(1)$$$

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

            he is trying to make joke about O(any constant) = O(1), and 10^6 log 10^6 is constant here

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

              Ok I get the joke. And well it is also true as there is the fact that the loop $$$10^6$$$ parts are not dependent on a variable taken from the input.

              → Ответить