Форум программистов, компьютерный форум, киберфорум
Наши страницы
Тамика
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Взялась за новый задачник :)

Запись от Тамика размещена 24.07.2019 в 13:53



Всегда рада критике и комментариям
Размещено в Без категории
Просмотров 303 Комментарии 3
Всего комментариев 3
Комментарии
  1. Старый комментарий
    Аватар для Avazart
    Сложность поиска в std::map вроде как O log(N), а O (1) это вставка.
    А вообще есть контейнер std::unordered_map !

    Если рассуждать логически и не пытаться бить лбом в лоб, наверное стоить предположить что:
    1. Входная последовательность довольно длинная, а иначе смысл? Т.е. худший вариант.
    2. В последовательности могут быть числа больше таргета, могут повторяться(дубликаты) - это опять же худший вариант.

    Поэтому вх.последовательность для начала имеет смысл отсортировать и удалить элементы больше суммы, удалить дубликаты(если это требует задание что вроде не сказано).

    Затем можно брать числа с краев вектора что в теории должно увеличить скорость нахождения пары.
    Можно вычислять число2 = таргет_сумма - число1 и искать "число2" либо просто поиском либо двоичным поиском.

    P.S.: Как насчет решить реальную прикладную задачу?
    Запись от Avazart размещена 25.07.2019 в 15:57 Avazart на форуме
    Обновил(-а) Avazart 25.07.2019 в 23:55
  2. Старый комментарий
    Цитата:
    Сообщение от Avazart Просмотреть комментарий
    Сложность поиска в std::map вроде как O log(N), а O (1) это вставка.
    А вообще есть контейнер std::unordered_map !
    Давненько не видела от Вас комментариев, спасибо, что заглянули!

    Это да, я планировала использовать std::unordered_map, потому ошиблась со сложностью Я внизу в комментарии предложила зрителям определить этот момент.

    Цитата:
    Если рассуждать логически и не пытаться бить лбом в лоб, наверное стоить предположить что:
    1. Входная последовательность довольно длинная, а иначе смысл? Т.е. худший вариант.
    2. В последовательности могут быть числа больше таргета, могут повторяться(дубликаты) - это опять же худший вариант.

    Поэтому вх.последовательность для начала имеет смысл отсортировать и удалить элементы больше суммы, удалить дубликаты(если это требует задание что вроде не сказано).

    Затем можно брать числа с краев вектора что в теории должно увеличить скорость нахождения пары.
    Можно вычислять число2 = таргет_сумма - число1 и искать "число2" либо просто поиском либо двоичным поиском.
    Не знаю насколько это лучше последнего варианта (который 0мс). Можно, ради интереса, сделать доп. выпуск и потестировать Ваш вариант. Заодно узнаем, насколько этот вариант выгоднее.
    Мне кажется, он проиграет, потому как в худшем случае оба алгоритма будут сложными, при том Ваш вариант с сортировкой - это как минимум O(logN), а вариант с мапой в худшем случае будет иметь линейную сложность. В лучшем, вариант 0мс будет выполнятся очень быстро, а Ваш всё ещё долго - пока сортировка, пока удаление дубликатов...

    Цитата:
    P.S.: Как насчет решить реальную прикладную задачу?
    Какую, например? У меня были мысли когда-то скачать проект опенсорсный и ковырять его, однако будет ли кому-то интересно наблюдать за этим?..
    Запись от Тамика размещена 29.07.2019 в 10:35 Тамика вне форума
    Обновил(-а) Тамика 29.07.2019 в 10:41
  3. Старый комментарий
    Аватар для Avazart
    Да предложенный мной вариант будет наверное такой же по скорости как и std::map и будет проигрывать std::unordered_map.


    Цитата:
    Какую, например? У меня были мысли когда-то скачать проект опенсорсный и ковырять его, однако будет ли кому-то интересно наблюдать за этим?..
    Текущее задание мне напомнило такую задачу:

    Представьте что у Вас есть список товаров в виде:

    "имя товара" | "стоимость товара за шт" | "кол-во товара, шт".

    Задача изменить цены товаров так что бы общая цена за все товары стала бы "без копеек" (что бы было удобно платить).Цену каждого товара при этом можно менять не более чем 0.5% от исходной.

    Понятно что при некоторых исх.данных у нас не всегда будет возможность получить результат, например при маленькой цене товаром и их количестве.

    Т.е. это по сути задачка для формирования чека. Я ее решил не с первого раза. И не уверен что мое решение прям самое оптимальное. Как мне кажется задача куда интереснее чем просто нахождение суммы.
    Запись от Avazart размещена 29.07.2019 в 11:03 Avazart на форуме
    Обновил(-а) Avazart 29.07.2019 в 19:20
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru