Насколько мы оптимизируем сложность времени?

Question

Теория против практики здесь. Что касается сложности времени, и у меня есть концептуальный вопрос, который мы не поняли go глубже в классе.

Вот оно:

Есть варвар c B ROOT алгоритм силы, O (n ^ 3) ... и мы понизили его o O (n), и это было сочтено достаточно хорошим. Если мы углубимся глубже, это фактически O (n) + O (n), две отдельные итерации ввода. Я придумал другой способ, который на самом деле был O (n / 2). Но эти два алгоритма считаются одинаковыми, поскольку оба являются O (n), и когда n достигает бесконечности, это не делает различий, поэтому вообще не нужно, когда мы достигаем O (n).

Мой вопрос :

В действительности, на практике у нас всегда есть конечное число входных данных (по общему признанию, иногда в триллионах). Таким образом, следуя логике временной сложности c, O (n / 2) в четыре раза быстрее, чем O (2n). Так что, если мы можем сделать это быстрее, почему бы и нет?

Answer 1

Сложность времени это еще не все. Как вы уже заметили, Big-Oh может многое скрывать, а также предполагает, что все операции стоят одинаково.

На практике вы всегда должны пытаться найти быстрое / самое быстрое решение для вашей проблемы. Иногда это означает, что вы используете алгоритм с плохой сложностью, но хорошими константами, если вы знаете, что ваша проблема всегда мала. В зависимости от вашего варианта использования вы также хотите реализовать оптимизацию, использующую свойства оборудования, такие как оптимизация кэша.