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

Автор alien_user, история, 22 месяца назад, По-английски

By calculating the time complexity of an algorithm, it is possible to check, before implementing the algorithm, that it is efficient enough for the problem. The starting point for estimations is the fact that a modern computer can perform some hundreds of millions of operations in a second.

For example, assume that the time limit for a problem is one second and the input size is n = 10^5. If the time complexity is O(n^2), the algorithm will perform about (10^5)^2 = 10^10 operations. This should take at least some tens of seconds, so the algorithm seems to be too slow for solving the problem.

On the other hand, given the input size, we can try to guess the required time complexity of the algorithm that solves the problem. The following table contains some useful estimates assuming a time limit of one second.

input size -> required time complexity

n ≤ 10 -> O(n!)

n ≤ 20 -> O(2^n)

n ≤ 500 -> O(n^3)

n ≤ 5000 -> O(n^2)

n ≤ 10^6 -> O(n log n) or O(n)

n is large -> O(1) or O(log n)

For example, if the input size is n = 10^5, it is probably expected that the time complexity of the algorithm is O(n) or O(n log n). This information makes it easier to design the algorithm, because it rules out approaches that would yield an algorithm with a worse time complexity

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

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

actually, there's some difference (little, but not minor) in $$$n \leq 10^5$$$ and $$$n \leq 10^6$$$, in the sense that they can cover the difference of $$$O(q \sqrt{n})$$$ and $$$O(q log n)$$$.

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

I think the correct range of n for O(n^2) is n ≤ 10^4. A good way to tell is if you plug in n, you should get around ~10^8 E.g. log10(n^2) = 8.00 for n = 10^4