Я хотел узнать больше о Big-O и нашел эту информацию:
'если f(x) = O(g(x)) скорость роста f(x) асимптотически меньше или равна скорости роста g(x)'
Что означает асимптотически в этом случае? Также мне трудно понять, почему Big-Theta не зависит от компьютера, который мы используем? Может ли кто-нибудь предоставить дополнительную информацию по этим двум вопросам?
Термин «асимптотически» в этом контексте относится к «по мере того, как x стремится к бесконечности». Когда кто-то говорит, что «f(x) растет асимптотически медленнее, чем g(x)», они имеют в виду, что при очень больших значениях x функция g(x) будет расти быстрее, чем функция f(x). Это означает, что для достаточно больших x, пока f(x) 1 и g(x) 1, значение g(x) всегда в конечном итоге будет больше, чем функция f(x).
Что касается этого вопроса:
Также мне трудно понять, почему Big-Theta не зависит от компьютера, который мы используем?
Хотя нотации O, , и широко используются в CS для описания сред выполнения, на самом деле они означают не это. Технически это обозначение используется для количественной оценки скорости роста функций, независимо от того, что на самом деле означают эти функции. Например, в аппроксимации Стирлинга в дискретной математике используется нотация с большой буквой O. который оценивает ln n! как n ln n - n + O(log n), где O(log n) означает «некоторую функцию, скорость роста которой равна O(log n)». В CS, когда мы говорим, что алгоритм — это O(n), на самом деле это означает, что «функция, описывающая время выполнения этой функции, равна O(n)». Точнее, вы увидите такие выражения, как «время выполнения алгоритма O(n)» или «алгоритм занимает время O(n)», подчеркивая, что нотация big-O используется для описания времени выполнения алгоритма, а не чем сам алгоритм. В этом смысле один ответ на ваш вопрос «почему нотация не зависит от компьютера?» «обозначение просто измеряет темпы роста функций и не имеет ничего общего с компьютерами».
С другой стороны, причина, по которой конкретный компьютер не имеет значения, заключается в том, что нотация говорит об асимптотическом времени выполнения, а не абсолютном времени выполнения. Если алгоритм имеет время выполнения (n), это означает, что время выполнения алгоритма масштабируется как некоторая линейная функция. Время выполнения этого алгоритма как размер входных данных может фактически быть чем-то вроде 100 n + 137 или 20 000 000 n - 15, потому что все, что имеет значение, — это то, как эти среды выполнения растут, а не сами среды выполнения. Если вы запускаете один и тот же код на разных компьютерах, его выполнение может занять больше или меньше времени в зависимости от выбранного компьютера, но почти наверняка линейное масштабирование не изменится на квадратичное. Это означает, что асимптотически время выполнения одинаковое, хотя абсолютно время выполнения может сильно различаться.
Надеюсь это поможет!
