Сообщение Re[3]: cpp и математика от 08.08.2016 7:35
Изменено 08.08.2016 7:40 Evgeny.Panasyuk
Здравствуйте, rg45, Вы писали:
R>>Я иногда спрашиваю во сколько раз сортировка 1млн элементов медленнее 100к элементов, и выгоняю тех кто не может посчитать двоичный логарифм от 10 или считает его по основанию e
R>А вот здесь я не понял. Исходя из оптимальной сложности сортировки O(n * log(n)), ответом будет 10 * log(1M) / log(100K). Мы вольны выбирать здесь любое удобное основание для логарифмирования, потому как отношение логарифмов не зависит от их основания и при любом основании будет одинаковым. И самым удобным в данном случае является не 2, и не e, а 10: 10 * 6 / 5 = 12. Поясни, пожалуйста, почему ты считаешь, что основание должно быть именно 2 и зачем вообще здесь нужно считать логарифм от десяти?
Во-первых вычислительная сложность выражается не только асимптотическими оценками, но и например точным/абсолютным ограничением на количество операций. Например std::partition_point делает не более log2(N)+2 сравнений. Ограничения на std::stable_sort также выражены через двоичный логарифм в абсолютном виде.
Во-вторых асимптотическая сложность Θ не даёт ответа на вопрос "во сколько раз медленнее N=100k vs N=1M" в прямом смысле, а лишь классификацию по классам эквивалентности.
R>>Я иногда спрашиваю во сколько раз сортировка 1млн элементов медленнее 100к элементов, и выгоняю тех кто не может посчитать двоичный логарифм от 10 или считает его по основанию e
R>А вот здесь я не понял. Исходя из оптимальной сложности сортировки O(n * log(n)), ответом будет 10 * log(1M) / log(100K). Мы вольны выбирать здесь любое удобное основание для логарифмирования, потому как отношение логарифмов не зависит от их основания и при любом основании будет одинаковым. И самым удобным в данном случае является не 2, и не e, а 10: 10 * 6 / 5 = 12. Поясни, пожалуйста, почему ты считаешь, что основание должно быть именно 2 и зачем вообще здесь нужно считать логарифм от десяти?
Во-первых вычислительная сложность выражается не только асимптотическими оценками, но и например точным/абсолютным ограничением на количество операций. Например std::partition_point делает не более log2(N)+2 сравнений. Ограничения на std::stable_sort также выражены через двоичный логарифм в абсолютном виде.
Во-вторых асимптотическая сложность Θ не даёт ответа на вопрос "во сколько раз медленнее N=100k vs N=1M" в прямом смысле, а лишь классификацию по классам эквивалентности.
Re[3]: cpp и математика
Здравствуйте, rg45, Вы писали:
R>>Я иногда спрашиваю во сколько раз сортировка 1млн элементов медленнее 100к элементов, и выгоняю тех кто не может посчитать двоичный логарифм от 10 или считает его по основанию e
R>А вот здесь я не понял. Исходя из оптимальной сложности сортировки O(n * log(n)), ответом будет 10 * log(1M) / log(100K). Мы вольны выбирать здесь любое удобное основание для логарифмирования, потому как отношение логарифмов не зависит от их основания и при любом основании будет одинаковым. И самым удобным в данном случае является не 2, и не e, а 10: 10 * 6 / 5 = 12. Поясни, пожалуйста, почему ты считаешь, что основание должно быть именно 2 и зачем вообще здесь нужно считать логарифм от десяти?
Во-первых вычислительная сложность выражается не только асимптотическими оценками, но и например точным/абсолютным ограничением на количество операций. Например std::partition_point делает не более log2(N)+2 сравнений. Ограничения на std::stable_sort также выражены через двоичный логарифм в абсолютном виде.
(при этом количество каких-то из операций необязательно прямо пропорционально затраченному времени на реальном железе, поэтому строго говоря нужно делать соответствующие оговорки)
Во-вторых асимптотическая сложность Θ не даёт ответа на вопрос "во сколько раз медленнее N=100k vs N=1M" в прямом смысле, а лишь классификацию по классам эквивалентности.
R>>Я иногда спрашиваю во сколько раз сортировка 1млн элементов медленнее 100к элементов, и выгоняю тех кто не может посчитать двоичный логарифм от 10 или считает его по основанию e
R>А вот здесь я не понял. Исходя из оптимальной сложности сортировки O(n * log(n)), ответом будет 10 * log(1M) / log(100K). Мы вольны выбирать здесь любое удобное основание для логарифмирования, потому как отношение логарифмов не зависит от их основания и при любом основании будет одинаковым. И самым удобным в данном случае является не 2, и не e, а 10: 10 * 6 / 5 = 12. Поясни, пожалуйста, почему ты считаешь, что основание должно быть именно 2 и зачем вообще здесь нужно считать логарифм от десяти?
Во-первых вычислительная сложность выражается не только асимптотическими оценками, но и например точным/абсолютным ограничением на количество операций. Например std::partition_point делает не более log2(N)+2 сравнений. Ограничения на std::stable_sort также выражены через двоичный логарифм в абсолютном виде.
(при этом количество каких-то из операций необязательно прямо пропорционально затраченному времени на реальном железе, поэтому строго говоря нужно делать соответствующие оговорки)
Во-вторых асимптотическая сложность Θ не даёт ответа на вопрос "во сколько раз медленнее N=100k vs N=1M" в прямом смысле, а лишь классификацию по классам эквивалентности.