Если алгоритм с O (n), то средняя сложность времени в среднем занимает 10 секунд для ввода размера 1000 элементов, сколько времени потребуется для выполнения, когда размер ввода составляет 10 000 элементов ?алгоритм усреднения временного интервала
Невозможно ответить .. И любой, кто действительно дает номер, является неправильным. Потому что Сложность времени is независимая базовой архитектуры машины. Вот почему мы игнорироватьзависит от машины константы.
Каждая платформа имеет свои собственные накладные расходы на выполнение определенных операций. Итак, опять же, ответ невозможно сказать.
«Поскольку временная сложность не зависит от базовой архитектуры машины» не оправдывает предыдущий оператор. O (n^2) не означает cn^2, но если это так (то, как ошибочно предполагают многие люди в CS или злоупотребляют обозначением), тогда мы могли бы определить c для этой машины с одной данной точки данных. Это не постоянно непознаваемо, и на практике мы не должны игнорировать. –
@DouglasZare - В этом случае мы не должны пытаться найти * фактическое время выполнения * на основе * временной сложности *. Просто скажите, что это за время. Потому что связь * Сложность времени * или * порядок роста * до фактического * времени работы * - это как просить - * Львы обычно спят по 20 часов в день .. Скажите мне, сколько времени Алекс лев спят каждый день * – TheLostMind
В вопросе говорилось, что фактическое время составляло 10 секунд для ввода размера 1000. Он не говорит, что нам нужно идти только от O (n^2) до фактического времени для ввода размера 10000. –
Хотя это не представляется возможным дать определенное число, а относится ко всем машинам, вы можете оценить, что O(n^2) должна быть около 100х для 10х увеличения n
Это идет с двумя важными оговорками
Привет, Питер, немного объяснений, пожалуйста? как больше в зависимости от времени, указанного выше? –
@IsayasNega Когда вы получаете доступ к данным в кэше CPU L3, каждый доступ может занять 10 нс, однако, если вы получаете доступ к данным в основной памяти, это может занять 70 нс. Это означает, что данные больше не вписываются в ваш кеш-память L3 (поскольку он больше) означает, что он на 7 раз медленнее навсегда. Если число обращений, равное 100x, получается на 700x медленнее. –
@ IsayasNega аналогичным образом доступ к основной памяти данных может занимать 70 нс, но доступ к диску может занимать 70 000 000 нс. Таким образом, если данные больше не вписываются в основную память, так как она в 10 раз больше, каждый доступ может быть на 10^6 раз медленнее. Если число обращений равно 100x, программа может занять 10^8 раз дольше. –
Обычно мы не связываем большой O с точным временем, но все же потребуется примерно 10^5 секунд, которые вы можете сказать (хотя и не правильно) time = a.n^2 найти по первому ограничению. Опять же, это не правильный метод, так как большой O отличается от точного времени, но все же он дает приблизительную оценку. – sashas
O (n^2) может быть функцией, равной 1000000 + 0,0001 (n^2). Поэтому теоретически вы не можете предсказать время просто по порядку сложности. Большая сложность O - это всего лишь мера того, как время растет асимптотически, поскольку N (размер ввода) стремится к бесконечности. –
Даже если вы знаете, что среднее время равно именно c.n^2, вы все равно не можете ответить на этот вопрос, хотя вы можете сказать, что такое оценка максимального правдоподобия. –