Комментарии 55
ответ на первый вопрос
1. кладем 8 шариков на весы по 4 на каждую чашу.
2. выкидываем 4, которые оказались легче.
3. кладем оставшиеся 4 шарика на весы по 2 на каждую чашу.
4. убираем по одному шарику с каждой чаши, выкидывая тот, что был взят с более легкой чаши.
5. в зависимости от от того, как изменится баланс весов, нужный шарик будет тот, который либо остался на более тяжелой чаше, либо окажется в руках.
2. выкидываем 4, которые оказались легче.
3. кладем оставшиеся 4 шарика на весы по 2 на каждую чашу.
4. убираем по одному шарику с каждой чаши, выкидывая тот, что был взят с более легкой чаши.
5. в зависимости от от того, как изменится баланс весов, нужный шарик будет тот, который либо остался на более тяжелой чаше, либо окажется в руках.
Это всё-таки три взвешивания :)
Можно обойтись двумя.
Можно обойтись двумя.
другой ответ на первый вопрос
1. берем шесть шариков по 3 на каждую чашу
2. если чаши равны, то искомый шарик в оставшихся двух
3. если не равны, то выкидываем три самых легких
4. взвешиваем 2 из оставшихся трех — задача решена :)
2. если чаши равны, то искомый шарик в оставшихся двух
3. если не равны, то выкидываем три самых легких
4. взвешиваем 2 из оставшихся трех — задача решена :)
Правильно. Это старая задачка. Более внушительно выглядит если нужно найти 1 шарик из 27 за 3 взвешивания.
более внушительно выглядит найти 1 шарик из 13 за 3 взвешивания, если не известно легче он или тяжелее.
В целом из задач только над 3 можно подумать. Остальные явно на позицию юниора не выше. Ну или во 2 искать точную формулу и пытаться убрать цикл (а возможно ли это?).
В целом из задач только над 3 можно подумать. Остальные явно на позицию юниора не выше. Ну или во 2 искать точную формулу и пытаться убрать цикл (а возможно ли это?).
Возможно.
Для примера из условия:
Доллар даёт одну шоколадку; шоколадка даёт одну обертку; одна обёртка даёт 1/3 шоколадки.
Тогда, при условии, что у нас бесконечное количество долларов, мы за каждый доллар получим:
1 + 1/3 + 1/9 + 1/27… шоколадок. Это убывающая геометрическая прогрессия. Если посчитать её сумму, то получим 1.5 шоколадки за каждый потраченный доллар.
Однако, у нас не бесконечное количество долларов. Для того, чтобы узнать, сколько шоколадок мы получим за один доллар, достаточно узнать, на каком шаге вычисления прогрессии мы остановимся:
x<=3: 1
3<x<=9: 1 + 1/3
9<x<=27: 1 + 1/3 + 1/9
…
Тогда решение задачи для примера из условия выглядит так:
x = 25
3^1 = 3 < x
3^2 = 9 < x
3^3 = 27 > x => нужно вычислить три шага
1 + 1/3 + 1/9 = 13/9
Теперь просто перемножаем: 15 * 13/9 = 21,6666666 ~ 21 (округляем всегда в меньшую сторону). Решение можно представить в обобщенном виде для любых «money, price, wrap».
Доллар даёт одну шоколадку; шоколадка даёт одну обертку; одна обёртка даёт 1/3 шоколадки.
Тогда, при условии, что у нас бесконечное количество долларов, мы за каждый доллар получим:
1 + 1/3 + 1/9 + 1/27… шоколадок. Это убывающая геометрическая прогрессия. Если посчитать её сумму, то получим 1.5 шоколадки за каждый потраченный доллар.
Однако, у нас не бесконечное количество долларов. Для того, чтобы узнать, сколько шоколадок мы получим за один доллар, достаточно узнать, на каком шаге вычисления прогрессии мы остановимся:
x<=3: 1
3<x<=9: 1 + 1/3
9<x<=27: 1 + 1/3 + 1/9
…
Тогда решение задачи для примера из условия выглядит так:
x = 25
3^1 = 3 < x
3^2 = 9 < x
3^3 = 27 > x => нужно вычислить три шага
1 + 1/3 + 1/9 = 13/9
Теперь просто перемножаем: 15 * 13/9 = 21,6666666 ~ 21 (округляем всегда в меньшую сторону). Решение можно представить в обобщенном виде для любых «money, price, wrap».
Я не прав. В написанном выше не учитываются возможные остатки на разных итерациях. После исправлений удалось найти решение для частного случая данных условий, но обобщить не получается :(
Приведите, пожалуйста, пример, где указанный вами выше подход не работает? Как один пример, когда формула работает: возьмем 14 уе, тогда 14*13/9=20.2(2), в ручную: 14 + 4 (две обертки в остатке) + 2 (2 обертки остатка, 4 обертки от второй партии) = 20.
Даже для исходного примера неправильно, как ниже заметил s_suhanov. Вроде удалось обобщить, проверил для 1 <= money <100000, 1 < price < 50, 2 < wrappers < 50— расхождений с итеративным алгоритмом нет. Буду рад, если кто-нибудь опровергнет.
Решение
Сначала нужно определить, сколько денег мы вообще можем потратить, так как обёртки в доллары не конвертируются.
На первой итерации каждый потраченный доллар гарантированно принесёт нам 1/price шоколадок. На второй: 1/price*wrappers и так далее. Снова получается геометрическая прогрессия. Первый шаг не зависит от wrappers, поэтому в прогрессию мы его не включаем. Теперь нужно посчитать s(n), — где n — это степень, при которой wrappers^n >= workMoney (по-хорошему, здесь должно быть просто «больше», но из-за потери точности даже в Decimal и округления вниз в некоторых ситуациях получается число вроде 47.9999999996 вместо 48), a0 = 1/wrappers * price.
Финальный шаг: сложим 1/price и s(n) и умножим на workMoney. Округляем в меньшую сторону.
Примеры:
money = 15, price = 1, wrappers = 3
workMoney = 15
n = 3, s(3)=1/3 + 1/9 + 1/27 = 14/27 ~ 0.4815
1 + 0.4815 = 1.4815
result = 15 * 1.4815 ~ 22.22 = 22
money=17, price = 3, wrapers = 5
WorkMoney = 15
n = 2, s(2) = 1/5*3 + 1/25*3 = 1/15 + 1/75 = 7/75
1/3 + 7/75 = 32/75 ~ 0.427
result = 15 * 0.427 ~ 6,3 = 6
Код:
На первой итерации каждый потраченный доллар гарантированно принесёт нам 1/price шоколадок. На второй: 1/price*wrappers и так далее. Снова получается геометрическая прогрессия. Первый шаг не зависит от wrappers, поэтому в прогрессию мы его не включаем. Теперь нужно посчитать s(n), — где n — это степень, при которой wrappers^n >= workMoney (по-хорошему, здесь должно быть просто «больше», но из-за потери точности даже в Decimal и округления вниз в некоторых ситуациях получается число вроде 47.9999999996 вместо 48), a0 = 1/wrappers * price.
Финальный шаг: сложим 1/price и s(n) и умножим на workMoney. Округляем в меньшую сторону.
Примеры:
money = 15, price = 1, wrappers = 3
workMoney = 15
n = 3, s(3)=1/3 + 1/9 + 1/27 = 14/27 ~ 0.4815
1 + 0.4815 = 1.4815
result = 15 * 1.4815 ~ 22.22 = 22
money=17, price = 3, wrapers = 5
WorkMoney = 15
n = 2, s(2) = 1/5*3 + 1/25*3 = 1/15 + 1/75 = 7/75
1/3 + 7/75 = 32/75 ~ 0.427
result = 15 * 0.427 ~ 6,3 = 6
Код:
private static int ChocolateCount(int money, int price, int wrappersPerOneChoco)
{
var workMoney = money - (money % price);
var stepsCount = 0;
int wrappers = 1;
while (wrappers <= workMoney)
{
stepsCount++;
wrappers = wrappers * wrappersPerOneChoco;
}
var chokosPerDollar = 1 / (double)price;
var additionalChokosByCurrentStep = 1 / (double)price;
for (int i = 0; i < stepsCount; i++)
{
additionalChokosByCurrentStep = additionalChokosByCurrentStep / wrappersPerOneChoco;
chokosPerDollar = chokosPerDollar + additionalChokosByCurrentStep;
}
return (int) (workMoney * chokosPerDollar);
}
Но ведь ответ не 21, а 22.
15 долларов == 15 шоколадок.
15 оберток == 5 шоколадок. (нарастающий итог == 20)
5 оберток == 1 шоколадка и 2 обертки (нарастающий итог == 21)
1 обертка от шоколадки и 2 обертки с пред. шага == 1 шоколадка (итог == 22).
Формула проста. Как было сказано, мы меняем 3 обвертки на 1 шоколадку+обвертку. Или по другому, мы получаем новую шоколадку ценой потери 2-х оберток. Но последние 2 обвертки мы поменять на шоколадку не можем, поэтому нужно 1 обвертку вычесть.
public static int calcChocoCount(int money, int price, int wrap){
int chocoByMoney = money/price;
return chocoByMoney + (chocoByMoney-1)/(wrap-1);
}
1. по 3 шарика
или весики уравновесятся или будет перевес
1.1 если уравновешены — значит тяжелый шарик один из двух оставшихся, просто взвешиваем их, находим нужный
1.2 если какие-то три перевесили, снова взвешиваем любые 2 из них
1.2.1 если весы уравновешены — тяжелый третий из этой выборки
1.2.2 если весы уехали — ниже тяжелый
Получили за 2 взвешивания
или весики уравновесятся или будет перевес
1.1 если уравновешены — значит тяжелый шарик один из двух оставшихся, просто взвешиваем их, находим нужный
1.2 если какие-то три перевесили, снова взвешиваем любые 2 из них
1.2.1 если весы уравновешены — тяжелый третий из этой выборки
1.2.2 если весы уехали — ниже тяжелый
Получили за 2 взвешивания
технически это три взвешивания)
возможный ответ на второй вопрос
если медведь упал с 10 метров за √2 секунды, то значит ускорение свободного падения в его местности равно 10 м/с^2, что немного расходится со всеми известными значениями для планеты Земля :) Но если брать максимальное значение, то оно находится на полюсе, а значит медведь скорее всего белый, так? :)
Еще один вариант на второй вопрос
Если медведь падает с ускорением меньше ускорения свободного падения, значит есть какая-то сила, действующая вверх, которая позволяет приземлиться без повреждений. Моя версия — это Винни-Пух спускается на шарике. Цвет возьмем из американской версии мультика — желтый/оранжевый.
Думается, всё несколько проще
Это бурый медведь, иначе где вы видели в Арктике деревья?
Так 10 — это больше, чем ускорение свободного падения. Оно 9.8 (различия полюс/экватор во втором знаке после запятой). Думаю, это просто округление до целых.
Возможно, дело в том что
под ground имеется ввиду не земля (в смысле почва), а некоторое основание, поверхность. Но раз медведь почему-то не получил повреждений (а падал без всяких шариков, о чем мы можем судить по ускорению, с которым он падал), то упал он на что-то мягкое. Например на толстый слой снега. Поэтому медведь белый.
Как-то все сложно…
Заголовок спойлера
Думаю, он просто упал в снег. Потому он белый. А свободное падение тут не при чем.
Бурые медведи живут там, где есть зимы и снег. А вот в местах обитания белых медведей деревьев не особо.
Деревьев нет, зато есть торосы и скалы. Впрочем, про снег подмечено верно.
Возникла еще мысль, что
повреждений нет, потому что медведь очень маленький. Птенцы выпадают из гнезд и порой остаются целыми. Маленькая масса — низкая энергия — нет повреждений. Самые мелкие детенышы у сумчатых (вики говорит, что у коалы — 5г), при этом детеныши розовые.
А еще нигде не сказано, что медведь не игрушечный.
Но больше всего смущает ускорение свободного падения. При нормальном ускорении он бы 10 метров пролетел за секунду с небольшим. А √2 это 1.414 примерно, так где он по пути задержался? Но опять же не сказано, что он мог по пути что-то задевать.
А еще можно сказать, что и бурые, и белые медведи с черной кожей, поэтому они черные!
В любом случае вопрос мне кажется довольно странным.
Но больше всего смущает ускорение свободного падения. При нормальном ускорении он бы 10 метров пролетел за секунду с небольшим. А √2 это 1.414 примерно, так где он по пути задержался? Но опять же не сказано, что он мог по пути что-то задевать.
А еще можно сказать, что и бурые, и белые медведи с черной кожей, поэтому они черные!
В любом случае вопрос мне кажется довольно странным.
Задача 3
int total_chocolate_count(int money_, int price_, int wrap_) {
int total_count = money_ \ price_;
int prev_count = total_count;
do {
total_count += prev_count \ wrap_;
prev_count = prev_count \ wrap_ + prev_count % wrap_;
}
while (prev_count \ wrap_ == 0)
return total_count;
}
За 1 доллар можно купить 1 1/3=4/3 шоколадки, за 15 долларов — 15*4/3=20 шоколадок. 2 фольги можно превратить в шоколадку: показать их продавцу и попросить шоколадку, которая будет тут же съедена и все 3 фольги отданы продавцу
исправление: за 3 фольги можно получить то же, что за 1 доллар, значит фольга стоит 1/3 доллара, а шоколадка без фольги — 2/3 доллара. За 15 долларов можно съесть 15/(2/3)=22.5 шоколадки без фольги. если есть фольга, то можно съесть 0.5 шоколадки следующим образом: найти компаньона с 1 фольгой, прийти в магазин, показать 2 фольги продавцу и попросить его шоколадку, отдать 2 фольги плюс фольгу из шоколадки продавцу, фольгу без шоколадки разделить с компаньоном
А для какого языка первая задачка вообще может представлять трудность?
Хотя вроде бы в чистом C, если не ошибаюсь, сих пор нет массивов и задачка предполагает что человек быстро накидает алгоритм сортировки байтиков?
Хотя вроде бы в чистом C, если не ошибаюсь, сих пор нет массивов и задачка предполагает что человек быстро накидает алгоритм сортировки байтиков?
Задача решается без массивов :)
Эффективнее было бы решить без использования массивов. Например, числа могут быть даны генератором.
А уж решение с сортировкой 100% будет завернуто как неэффективное.
А уж решение с сортировкой 100% будет завернуто как неэффективное.
Но ведь для определения кто из них меньший, а кто больший, мы уже должны иметь все цифры на руках? А готовый набор данных сам по себе является массивом по определению?
Прошу прощения, если вопрос глупый, я больше ит-менеджер и программированием интересуюсь только контексте автоматизации рутинных задач.
Прошу прощения, если вопрос глупый, я больше ит-менеджер и программированием интересуюсь только контексте автоматизации рутинных задач.
Но ведь для определения кто из них меньший, а кто больший, мы уже должны иметь все цифры на руках?Да, должны. Но нам не обязательно их в массив сохранять, можем просто пробежаться циклом, экономия памяти выйдет. Представьте, например, что мы получаем 1 млрд 64-битных чисел по сети и из них нужно найти минимум. Просто сохранить их в массиве займет ~8 гб оперативной памяти, а пробежаться по ним циклом займет три переменных.
Ну а насчет сортировки — она делается за O(NlogN), что гораздо дольше, чем O(N).
Провел эксперимент:
Пусть у нас есть
генератор, выдающий числа
И мы хотим найти минимум и максимум среди первых 1 млрд чисел, порожденных этим генератором.unsigned long long generator() {
static unsigned long long x = 0; // Предыдущее сгенерированное число
return x = x * 239017u + 170239u; // Текущее сгенерированное число
}Вариант 1: отсортировать и взять первый и последний элементы
double start = clock(); // Запоминаем момент начала
std::vector<unsigned long long> numbers; // Массив для чисел
numbers.reserve(SIZE); // Выделяем память, без этого будет работать дольше
std::generate_n(std::back_inserter(numbers), SIZE, generator); // Генерируем 1 млрд чисел
std::sort(numbers.begin(), numbers.end()); // Сортируем
std::cout << numbers[0] << ' ' << numbers[SIZE - 1] << std::endl; // Выдаем ответ
std::cout << (clock() - start) / CLOCKS_PER_SEC << std::endl; // Выдаем времяВариант 2: найти минимальный и максимальный элементы циклом
double start = clock(); // Запоминаем момент начала
std::vector<unsigned long long> numbers; // Массив для чисел
numbers.reserve(SIZE); // Выделяем память, без этого будет работать дольше
std::generate_n(std::back_inserter(numbers), SIZE, generator); // Генерируем 1 млрд чисел
auto mm = std::minmax_element(numbers.begin(), numbers.end()); // Находим минимум и максимум
std::cout << *mm.first << ' ' << *mm.second << std::endl; // Выдаем ответ
std::cout << (clock() - start) / CLOCKS_PER_SEC << std::endl; // Выдаем времяВариант 3: найти минимальный и максимальный элементы циклом, не запоминая их в массив
Вот и получается: можно использовать гораздо (асимптотически) меньше как памяти, так и времени работы. Поэтому вариант решения «запомнить все в массив, отсортировать, взять первый и последний» я называю неоптимальным.double start = clock(); // Запоминаем момент начала
unsigned long long min = std::numeric_limits<unsigned long long>::max();
unsigned long long max = std::numeric_limits<unsigned long long>::min();
for (int i = 0; i < SIZE; ++i) { // Цикл по всем числам
unsigned long long x = generator(); // Генерируем очередное число
min = std::min(min, x); // Обновляем минимум
max = std::max(max, x); // Обновляем максимум
}
std::cout << min << ' ' << max << std::endl; // Выдаем ответ
std::cout << (clock() - start) / CLOCKS_PER_SEC << std::endl; // Выдаем времяА для какого языка первая задачка вообще может представлять трудность?
Хотя вроде бы в чистом C, если не ошибаюсь, до сих пор нет массивов и задачка предполагает что человек быстро накидает алгоритм сортировки байтиков?
Хотя вроде бы в чистом C, если не ошибаюсь, до сих пор нет массивов и задачка предполагает что человек быстро накидает алгоритм сортировки байтиков?
.
то ли я лагаю, то ли хабр. Ну пусть буду я. Про C уже посмотрел, что там есть массивы
1. Вопрос.
Взвешиваем любые 3 и 3. Если они одинаковые, то взвешиваем оставшиеся 2. Находим тяжелый.
Если одна из троек тяжелее, то взвешиваем два шарика из «тяжелой» тройки. Любые. В результате искомый шар будет или одним из двух, или оставшимся, не взвешенным.
Взвешиваем любые 3 и 3. Если они одинаковые, то взвешиваем оставшиеся 2. Находим тяжелый.
Если одна из троек тяжелее, то взвешиваем два шарика из «тяжелой» тройки. Любые. В результате искомый шар будет или одним из двух, или оставшимся, не взвешенным.
2. Любого или грязного. Например, если медведь игрушечный.
3. 22 шоколадки. Сначала 15, потом 5, потом 1. Потом остается две обертки от 5 и одна от последней. Итого 22.
Да уж. В этом выпуске задачи просто поразили.
Задача с произведением мин-макс меня вгоняет в ступор. Если там нет дополнительных ограничений, и в задаче нужно найти минимальный элемент, максимальный элемент, и просто перемножить, то смысла в задаче не вижу.
Задача с 2 компами вероятно дана для общения между кандидатом и принимающей стороной. В этом задаче нет некоторых пояснений, например какой объем дополнительной памяти можно использовать и какой приоритет (время работы, простота алгоритма, время написания кода). Есть ли смысл выкладывать сюда задачи такого типа, если автор не может выступить полноценно второй стороной?
Решения мои
Задача с произведением мин-макс меня вгоняет в ступор. Если там нет дополнительных ограничений, и в задаче нужно найти минимальный элемент, максимальный элемент, и просто перемножить, то смысла в задаче не вижу.
Задача с 2 компами вероятно дана для общения между кандидатом и принимающей стороной. В этом задаче нет некоторых пояснений, например какой объем дополнительной памяти можно использовать и какой приоритет (время работы, простота алгоритма, время написания кода). Есть ли смысл выкладывать сюда задачи такого типа, если автор не может выступить полноценно второй стороной?
Решения мои
Заголовок спойлера
Вопрос 1.
Вопрос 2.
Задача 1. Решение слишком очевидно, чтобы его приводить.
Задача 2. Там тоже все просто, переводим бабло в шоколадки. А дальше в цикле переводим шоколадки в обвертки, а их опять в шоколадки по курсу.
Задача 3.
Заголовок спойлера
В общем виде за n взвешиваний можно найти шарик среди не более 3^n штук. Таким образом за 2 взвешивания можно найти нужный шарик из 9. Кол-во 8 дано с целью запутать человека, чтобы он решал вопрос в степенях двойки.
Вопрос 2.
Заголовок спойлера
Я вижу 2 формально удовлетворяющих заданию ответа, которые дают взаимоисключающие результаты. g=10м/c^2 — это округление (также как и пи не равно 3.14). Цель этой части показать, что гравитация в зоне медведя существует, т.е. он в нормальных условиях свернет себе шею.
белый
Медведь не разбивается, если приземлится в снег или воду( есть ещё песок, но это так). Если бы он приземлился в воду, тогда в условиях написали бы «достиг воды», а не земли. Значит он находится где-то заполярном круге. И Обычно это белые медведи.
Медведь желтый, розовый, коричневый, фиолетовый. Какой угодно, но не белый. Потому что ...
это мишка Гамми.
Задача 1. Решение слишком очевидно, чтобы его приводить.
Задача 2. Там тоже все просто, переводим бабло в шоколадки. А дальше в цикле переводим шоколадки в обвертки, а их опять в шоколадки по курсу.
Задача 3.
Заголовок спойлера
А вот тут нужно знать, чего от тебя хотят. Получить алгоритм с лучшим классом алгоритмической сложности, алгоритм за меньшее время (при данных условиях важна константа), или подойдет самый примитивный алгоритм. В принципе, если работа единовременная, то написать решение за 5 минут, и оставить работать обе машины на ночь — это будет самым разумным вариантом. В каждом из 3-х случаев я бы дал разное решение.
Предположим, что у нас уже есть 2 компа с уже отсортированными (на каждом из них) данными. В цикле проходим по обоим массивам на первой машине начинаем с начала, а на второй с конца. Рано или поздно число в на первой машине станет меньше числа на второй. Вот мы и нашли ту границу, по которой нужно числа со второго компа отправлять на первый, и наоборот. Могу написать алгоритм, который без дополнительной памяти (ну несколько переменных) путем замены ячеек сделает из двух упорядоченных массивов один за линейное время.
Но если мы можем это сделать(из 2-х упорядоченных сделать один), то автоматом решается и все предыдущие этапы задачи. Т.е. сначала разбиваем весь массив на пары и упорядочиваем. Затем пары объединяем в четверки, их уже в 8-ки и так далее, пока не получим цельный алгоритм. Если алгоритм слияния линейный, тогда сложность всего алгоритма — N*ln2(N).
С другой стороны можно пройтись по всему не отсортированному массиву, посчитать кол-во значений у которых первый бит =1. Зная это значение, можно перенести такие значения вверх, а оставшийся вниз. Хотя наверное, для этого даже считать их кол-во не нужно, нужно только знать границы массива. Далее в каждом из получившихся групп проводим сортировку по второму биту и так далее. Каждая операция сортировки по биту выполняется за O(n). Итого на подготовительную операцию уходит O(N*ln2(M)), где M — это максимальное значение типа, а ln2(M)- количество бит. И пусть M>N, но разница не большая, и будет важна константа алгоритмической сложности.
Надо будет посмотреть, сколько займет на этих данных пузырьковая сортировка, ради интереса.
Предположим, что у нас уже есть 2 компа с уже отсортированными (на каждом из них) данными. В цикле проходим по обоим массивам на первой машине начинаем с начала, а на второй с конца. Рано или поздно число в на первой машине станет меньше числа на второй. Вот мы и нашли ту границу, по которой нужно числа со второго компа отправлять на первый, и наоборот. Могу написать алгоритм, который без дополнительной памяти (ну несколько переменных) путем замены ячеек сделает из двух упорядоченных массивов один за линейное время.
Но если мы можем это сделать(из 2-х упорядоченных сделать один), то автоматом решается и все предыдущие этапы задачи. Т.е. сначала разбиваем весь массив на пары и упорядочиваем. Затем пары объединяем в четверки, их уже в 8-ки и так далее, пока не получим цельный алгоритм. Если алгоритм слияния линейный, тогда сложность всего алгоритма — N*ln2(N).
С другой стороны можно пройтись по всему не отсортированному массиву, посчитать кол-во значений у которых первый бит =1. Зная это значение, можно перенести такие значения вверх, а оставшийся вниз. Хотя наверное, для этого даже считать их кол-во не нужно, нужно только знать границы массива. Далее в каждом из получившихся групп проводим сортировку по второму биту и так далее. Каждая операция сортировки по биту выполняется за O(n). Итого на подготовительную операцию уходит O(N*ln2(M)), где M — это максимальное значение типа, а ln2(M)- количество бит. И пусть M>N, но разница не большая, и будет важна константа алгоритмической сложности.
Надо будет посмотреть, сколько займет на этих данных пузырьковая сортировка, ради интереса.
.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Выпуск#7: ITренировка — актуальные вопросы и задачи от ведущих компаний