При повторении набора чисел время будет увеличиваться с постоянной экспоненциальной скоростью

Привет, хорошие люди из stackoverflow, это концептуальный вопрос, который, возможно, относится к math.stackexchange.com, однако, поскольку это относится к скорости обработки процессора, я поместил его здесь.

В любом случае, мой вопрос довольно прост. Мне нужно вычислить сумму кубов 3 чисел в диапазоне чисел. Меня это сбивает с толку, поэтому позвольте мне привести пример.

У меня есть диапазон чисел (0, 100) и список каждого куба чисел. Я должен рассчитать каждую комбинацию из 3 чисел в этом наборе. Например, 0 + 0 + 0, 1 + 0 + 0, ... 98^3 + 99^3 + 100^3. Это может иметь смысл, я не уверен, что объяснил это достаточно хорошо.

В любом случае, после того, как все наборы вычислены и сверены со списком чисел, чтобы увидеть, совпадает ли сумма с каким-либо из них, программа переходит к следующему набору (100, 200). Этот набор должен вычислять все от 100-200 + 0-200 + 0-200. Затем (200, 300) нужно будет сделать 200 - 300 + 0 - 300 + 0 - 300 и так далее.

Итак, мой вопрос: в зависимости от чисел, данных ЦП для добавления, увеличится ли время, затрачиваемое на размер? И будет ли время, необходимое для каждого набора, экспоненциально увеличиваться с предсказуемой скоростью или оно будет экспоненциальным, но не постоянным.


person Matt Habel    schedule 03.06.2011    source источник
comment
Обратите внимание, что проверка по списку чисел, чтобы увидеть, совпадает ли сумма с каким-либо из них, не является бесплатной операцией. В зависимости от структуры данных, используемой для хранения этого набора, эта проверка может иметь время выполнения в диапазоне от O (1) до O (n) (где n — количество различных сумм, которые сохраняются).   -  person Michael McGowan    schedule 03.06.2011


Ответы (3)


Время сложения двух чисел логарифмически зависит от величины чисел или линейно зависит от размера (длины) чисел.

Для 32-битного компьютера числа до 2^32 будут складываться за 1 единицу времени, числа до 2^64 — за 2 единицы и т. д.

person Gabe    schedule 03.06.2011

Насколько я понимаю, у вас есть примерно 100 * 100 * 100 комбинаций для первого набора (давайте проигнорируем, что сложение является коммутативным). Для следующего сета у вас 100*200*200, а для третьего у вас 100*300*300. Итак, похоже, что у вас там происходит процесс O (n ^ 2). Так что если вы хотите рассчитать в два раза больше сетов, это займет у вас в четыре раза больше времени. Если вы хотите вычислить в три раза больше, это займет в девять раз больше времени. Это не экспоненциальное (например, 2 ^ n), а обычно называемое квадратичным.

person wxffles    schedule 03.06.2011

Это зависит от того, как долго длится "и так далее". Пока ваше максимальное число в кубе соответствует вашему самому длинному целочисленному типу, нет. Для добавления всегда требуется только одна инструкция, поэтому это постоянное время.

Теперь, если вы предполагаете машину с произвольной точностью, например, запись этих чисел на ленту машины Тьюринга в десятичных символах, то сложение займет больше времени. В таком случае подумайте, сколько времени это займет? Другими словами, подумайте о том, как увеличивается длина строки десятичных символов, чтобы представить число n. Это займет время, по крайней мере, пропорциональное этой длине.

person Charlie Martin    schedule 03.06.2011
comment
Итак, если набор чисел будет продолжаться, скажем, до 80 цифр, то количество времени, необходимое для добавления 3, займет такое же количество времени процессора? И вы на самом деле не ответили на мой другой вопрос, если время, необходимое для каждого нового набора чисел, будет увеличиваться с постоянной экспоненциальной скоростью. - person Matt Habel; 03.06.2011