Нотация Big O зависит только от размера матрицы или типа данных (целое число, логическое значение)?

Question

Зависит ли большое обозначение O только от размера матрицы? или это также будет зависеть от типа данных (целое или логическое).

Предположим, если у меня есть две матрицы размера mat = M x N, и я должен их умножить. Если тип данных матрицы целочисленный, время выполнения на компьютере отличается, но если тип данных является логическим [+ 1, -1], время выполнения на компьютере сокращается. Как я могу написать большую букву O, учитывая также тип данных.

Answer 1

Вы не принимаете это во внимание;big-O одинаков во всех случаях. Big-O составляет около , масштабирование ;сколько больше работы вы выполняете при увеличении размера входных данных относительно базовой работы?

Если алгоритм не масштабируется до произвольных длин битов для каждого элемента матрицы, разницамежду булевыми и целыми числами будет постоянный множитель, а постоянные множители игнорируются в нотации big-O. Для выбора 16 против 8 против 2 против 1 это не совсем произвольный рост;16 бит могут занимать в 16 раз дольше 1 бита для матрицы 10x10, но если для 20x20 это также занимает 16 раз больше 1 бита, коэффициент масштабирования такой же.

Примечание. На реальном оборудовании, могут быть более заметные изменения в производительности (матрицы, которые перестают помещаться в строке кэша или вообще в кэше, могут существенно изменить поведение), но big-O - это идеализированные вычислительные устройства, без таких ограничений.