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

Mo's algorithm definition not cleared

Автор ajains, история, 6 лет назад, По-английски

Why do we take sqrt(N) as block size in algorithm suppose i take 5 as block size what would be the difference?

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

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

We are given queries(expressed as [l,r] interval, 1<=l<=r<=n) and sort them with group number that l is in, if same sort with r. suppose number of groups is g and block size is b. (g * b == q)

We will answer query by moving left and right pointer, and we will count number of moves of each pointer. left pointer will move O(q * b) times.(worst when left pointer iterate whole block for each query) right pointer will move O(g * n) times. (worst when right cursor iterate whole sequence for each block that left pointer is at. Right pointer is only increasing when left pointer is in same block.)

we choose b = sqrt(n) so time complexity will be O((n+q) sqrt(n))

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

    g * b == q if we maintain this we will be getting appropriate time complexity right?

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

      Actually g * b = n, since you turn the complete array into g groups of size b. (DongwonShin wrote q by accident.) And that's just a fact. Maintaining this will not give you the optimal complexity, but just making sure that the algorithm works at all.

      The most important thing is that by sorting the queries in the special way, the complexity will be O(q·b + g·n) (see DongwonShin's explanation).

      So the important question is, what is the optimal block size such that the algorithm will run the fastest.

      If you for instance pick 5 as block size, then you will have the complexity O(q·5 + n / 5·n) = O(n2), which will be pretty bad. Turns out that if q ≈ n, then the optimal choice is . This gives the total complexity .

      → Ответить