Блог

Я работаю над анализом временной сложности алгоритма. Я не уверен, каков правильный способ вычисления с учетом временной сложности основных операций, таких как сложение и вычитание двух чисел. Я узнал, что временная сложность сложения двух n-значных чисел равна O(n), потому что именно столько элементарных битовых операций вам нужно выполнить во время сложения. Однако недавно я услышал, что в настоящее время в современных процессорах время, затрачиваемое на сложение двух чисел любого размера (которое все еще управляется компьютером), является постоянным: оно не зависит от размера двух чисел. Следовательно, при анализе временной сложности алгоритма вы должны рассчитать временную сложность сложения двух чисел любого размера как O(1). Какой подход является правильным? Или в случае, если ответ заключается в том, что оба подхода «правильны», используемые в соответствующем контексте, какой подход более приемлем в исследовательской работе? Заранее благодарю вас за любой ответ.

Это зависит от типа алгоритма, который вы анализируете, но в общем случае вы просто предполагаете, что входные данные анализируемого алгоритма будут соответствовать размеру слова машины, на которой он будет выполняться (будь то 32 бит, 128 бит, что угодно), и в соответствии с этим предположением, когда любая отдельная арифметическая операция, вероятно, будет выполняться как одна машинная инструкция и вычисляться за одно или небольшое постоянное число тактов процессора, независимо от базовой сложности аппаратной реализации, вы будете рассматривать сложность этой операции как O(1). То есть вы бы предположили сложность O(1) для арифметических операций, если только нет особых причин предполагать, что они не могут быть обработаны за постоянное время.

Вы действительно нарушили бы предположение O(1) только в том случае, если бы специально разрабатывали алгоритм, который будет выполняться на числовых входах произвольной точности, так что вы планируете самостоятельно программно вычислять арифметические операции, а не полностью передавать их аппаратному обеспечению (ваш алгоритм ожидает переполнения/переполнения и предназначен для их обработки), или если бы вы работали на уровне реализации этих операций самостоятельно в схеме ALU или FPU. Затем, независимо от того, выполняется ли умножение за O(n*logn) или O(n*logn*loglogn) время в количестве битов, на самом деле будет иметь значение для вашего анализа сложности: потому что количество битов, участвующих в этих операциях, не ограничено некоторой константой, или вы специально анализируете сложность алгоритма/аппаратного обеспечения, которое само реализует арифметическую операцию.