По Python пайтон
Во сколько раз (примерно) возрастёт время работы алгоритма сложностью O(n2)по сравнению O(n * log ((n)) с на входных данных размера n=10000? Ответ округлите до целого. Помните также, что логарифм берётся по основанию 2.
смотрел таблицы но не допонял
Все О-большие оцениваются с точностью до константного множителя, поэтому сама постановка вопроса "во сколько раз" некорректна, даже примерно.
Например, если у нас 1000 × n² операций, то это O(n²). И если 0.01 × n² операций, это тоже O(n²). И 1000000 × n² операций - тоже O(n²).
С логарифмом - полностью аналогичная история.
Более того, расчёт конкретного количества операций упирается не только в множитель, но и в слагаемые меньшего порядка. Например, O(n² + 400n) - тоже квадратичный алгоритм. И O(n² + n log n) - квадратичный.
Можем это решить формально в общем виде при некоторых допущениях.
Допустим, слагаемые меньшего порядка отсутствуют, а O(n²) соответствует C × n² операций.
А O(n log n) соответствует B × n × log₂ n операций.
Тогда надо найти
C × n² / (B × n × log₂ n) = C / B × n / log₂ n ≈
≈ C / B × 10000 / 13.288 ≈
≈ C / B × 752.57 А дальше всё зависит от соотношения указанных констант.
Для более сложных формул принцип тот же - делим одно на другое, сокращаем общие множители, подставляем конкретное значение n.
И само собой, оценка асимптотической сложности не зависит от используемого языка. Так же, как выражение 2 + 2 = 4 от него не зависит.
