У меня возникли проблемы с назначением относительно времени выполнения.Время выполнения для алгоритма, суммирующего целые числа
Заявление о проблемах: «Изабель имеет интересный способ суммирования значений в массиве A из n целых чисел, где n - степень 2. Она создает массив B, равный половине A, и множества B [i] = A [2i] + A [2i + 1], для i = 0,1, ..., (n/2) -1. Если B имеет размер 1, то она выдает B [0]. , она заменяет A на B и повторяет процесс. Каково время ее алгоритма? "
Будет ли это рассматриваться как O (log n) или O (n)? Я думаю, что O (log n), потому что вы продолжаете разделять массив пополам, пока не получите окончательный результат, и я считаю, что основа O (log n) заключается в том, что вы не проходите всю структуру данных. Однако, чтобы вычислить сумму, вы должны получить доступ к каждому элементу массива, что заставляет меня думать, что это может быть O (n). Любая помощь в понимании этого была бы весьма признательна.
Это, безусловно, домашнее задание ... Я думаю, нам следует избегать явного ответа на эти проблемы. –
@GeorgeSkoptsov Я согласен, и я думаю, что ваш ответ был лучше моего.Было много обсуждений по мета-вопросам о том, как решать домашние вопросы, и я вспоминаю, что они должны рассматриваться как обычные вопросы. Но я мог ошибаться (или политика могла измениться) – mgibsonbr
Хех, я не следую мета ... Я не согласен с этой политикой. Я могу понять, помогая кому-то двигаться вперед с проблемой, но не предоставляя решение человеку, которому явно было предложено вывести его на свой страх и риск. –