Худшее время работы (Big O)

Question

У меня есть этот вопрос, и я не знаю, как его решить, потому что я его не понимаю. (

Вопрос:

Программы A и B проанализированы и, как установлено, имеют наихудшее время выполнения не более 150 n log n и n ² соответственно Ответьте на следующие вопросы:

i) Какая программа имеет лучшую гарантию на время работы для больших значения n ( n > 10000)?

ii) Какая программа имеет лучшую гарантию на время работы для малых значения n ( n <100)? </p>

Может ли кто-нибудь помочь мне и объяснить это для меня?

Answer 1

Вам даны две формулы и два разных значения n для подключения к ним. Затем вас спросят, какая формула имеет большее значение в каждом случае.

Я предлагаю включить в формулы два значения n и выяснить, какое из них больше в каждом случае.

Answer 2

Вы смотрели на график двух функций сложности ?

Answer 3

Если фактический вопрос O (n ^ 2), ii - вопрос с подвохом.

В записи Big-O вы можете отбрасывать константы, поэтому O (10000n ^ 2) совпадает с O (n ^ 2). Если вы не удалили O () из вопроса, просто заполните уравнения, это не должно быть сложно.

Answer 4

См. Себя в WolframAlpha .Точка, в которой худшие случаи равны, - около 1042. Это должно ответить на ваш вопрос.

Answer 5

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