Когда O (n * n) будет быстрее, чем O (log n)?

Question

У меня есть этот вопрос на практическом тесте, и я не уверен, когда код будет работать быстрее на O (n * n) по сравнению с O (log n).

Answer 1

Большой ой нотации дает верхние границы.Не более.

Если алгоритм A равен O(n ^ 2), он может потребовать ровно n ^ 2 шагов.

Если алгоритм B равен O(log n), он может потребовать ровно 10000 * log n шагов.

Алгоритм A намного быстрее, чем алгоритм B для малых n.

Answer 2

Я отказываюсь от своего предыдущего ответа никогда, потому что с технической точки зрения алгоритм O(n*n) может быть быстрее, чем алгоритм O(log n), хотя и невероятно. Посмотрите мое обсуждение с Иисусом под его ответом для более подробной информации. На графике ниже показано, что алгоритм, который имеет временную сложность точно log n, всегда быстрее, чем алгоритм, который имеет временную сложность точно n*n.

Answer 3

Помните, что Big-O - это верхняя граница.Вполне возможно, что из-за констант, что при меньших входных размерах алгоритм O (n ^ 2) может работать быстрее, чем O (log n).Вполне возможно, что в большинстве случаев n ^ 2 также может работать быстрее и что алгоритм работает в n ^ 2 только из-за определенных входных наборов, которые заставляют его выполнять большую работу.