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

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

For this Problem

1829E - The Lakes

The solution is written in O(n*m)

But How it is possible if there is recursion calls inside the nested solution.

Solution in tutorial is:

https://codeforces.net/blog/entry/116108 (Problem E)

Please someone help me understand the time complexity?Shouldn't it be O(n*m*n*m).I know we are not checking same grid twice.

Please someone help me.

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

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

each cell will be visited at most once

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

    I know that.But I am not understanding if there is recursion calls in that O(n*m) nested loop.Shouldn't it be O(n*m*recursioncalls).

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

      No. Loop counts do not matter. Its all about sum. Think of it this way.

      """Given a tree with n nodes and a value for each node ai, calculate the sum of values of their children for each node.

      Take a look at this pseudocode.

      vector<int> ans(n+1);

for (int i=1;i<=n;i++) {
    for (int neighbor : edges[node]) {
        if (neighbor!=parent) {
            ans[node]+=a[neighbor];
        }
    }
}

      This piece of code has n loops and it seems like every node can have upto n neighbors so its O(N^2) right? No. Because the sum of neighbor counts of each node is fixed and is linear. So it is O(N).

      The same logic can be applied here.

      → Ответить