время работы алгоритма с учетом временной сложности

Question

время работы алгоритма с учетом временной сложности

алгоритмы
асимптотика
Математика
анализ-алгоритмов
вычислительная сложность

Тая Мбо

c) Предположим, что алгоритмы A1 и A2 имеют вычислительную сложность $O(n \log(n))$ и $O(n^3)$ соответственно. Оба алгоритма занимают примерно $100$ секунд для запуска при вводе данных размером $n = 10,000$ . Определите (с точностью до секунды) время, которое потребуется каждому алгоритму для запуска на входных данных размера

я. $n = 1,000$

II. $n = 100$

Последние несколько дней я пытался найти способ решить эту проблему, но я полностью застрял. У кого-то была аналогичная проблема, но когда я попытался использовать их метод, это не сработало. Пожалуйста, помогите, у меня экзамен по этому во вторник

Фабио Соменци

Во-первых, нотация большого О дает только верхние границы. Насколько нам известно, оба алгоритма могут работать за линейное время. Второй,

f_{1} (n) = k_{1} n \log (n)

$f_1(n) = k_1 n \log(n)$ и

f_{2} (n) = k_{2} n \log (n) + 99

$f_2(n) = k_2 n \log(n) + 99$ оба

O (n \log (n))

$O(n \log(n))$ , но если

f_{1} (10^{4}) = f_{2} (10^{4}) = 100

$f_1(10^4) = f_2(10^4) = 100$ , затем

k_{1} = 100 k_{2}

$k_1 = 100 k_2$ и время их выполнения для

n = 10^{3}

$n=10^3$ или

n = 10^{2}

$n=10^2$ будет очень разным.

Ответы (1)

время работы алгоритма с учетом временной сложности

Во-первых, нотация большого О дает только верхние границы. Насколько нам известно, оба алгоритма могут работать за линейное время. Второй, $f_1(n) = k_1 n \log(n)$ и $f_2(n) = k_2 n \log(n) + 99$ оба $O(n \log(n))$ , но если $f_1(10^4) = f_2(10^4) = 100$ , затем $k_1 = 100 k_2$ и время их выполнения для $n=10^3$ или $n=10^2$ будет очень разным.

bsbb4 · Answer 1

Пожалуйста, имейте в виду, что я почти ничего не знаю о вычислительной сложности.

Давайте вызовем среды выполнения для ввода размера $n$ $A_1(n)$ и $A_2(n)$ соответственно. Нам дано, что $A_1(n) = O(n\log(n))$ Который означает, что $\lim_{n \to \infty}\frac{A_1(n)}{n\log(n)} < \infty$ . Следовательно, предел конечен, но мы еще не знаем, что это такое. Мы можем понять это, используя дополнительную информацию, которую нам дают: $A_1(10) = 100$ . Подключаем, получаем $\frac{A_1(10)}{10\log(10)} \approx 4.3429$ . Делая то же самое для $A_2$ мы получаем $\frac{A_2(10)}{10^3} = 0.1$ .

Теперь мы можем решить проблему:

\frac{А_{1} (1000)}{1000 бревно (1000)} "=" 4.3429 ⟹ А_{1} (1000) \approx 30 000

$\frac{A_1(1000)}{1000\log(1000)} = 4.3429 \implies A_1(1000) \approx 30\,000$

\frac{А_{2} (1000)}{1000 бревно (1000)} "=" 0,1 ⟹ А_{2} (1000) "=" 100 000 000

$\frac{A_2(1000)}{1000\log(1000)} = 0.1 \implies A_2(1000) = 100\,000\,000$

Вторая часть вопроса работает так же.

время работы алгоритма с учетом временной сложности

Тая Мбо

Фабио Соменци

Ответы (1)

bsbb4

Ожидаемое время быстрой сортировки

Что означает слово «масштабируемость» с точки зрения Big O?

Расчет времени выполнения по временной сложности

Время выполнения быстрой сортировки

Как сформулировать рекуррентное уравнение для времени работы алгоритма «разделяй и властвуй»

Сложность алгоритма — цикл for внутри цикла while; уменьшается в 2 раза

Какова временная сложность при равномерной выборке записей bbb без замены записей nnn?

Сравнение временной сложности двух алгоритмов (неравенство)

Вопрос, связанный с суммированием и Θ-обозначением времени работы

Что именно представляет собой наихудший ввод различных алгоритмов сортировки?