Задать вопрос
  • Можно ли добиться постоянного O(nlogn) для квиксорта в любом случае?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Да, можно. Для этого надо в качестве pivot'а выбрать медиану. если это сделать за O(n) в худшем случае, то общая сложность QuickSort'а будет O(n log n).

    Для выбора медианы за O(n) есть, например, вот такой алгоритм. В каких-то источниках его еще называли алгоритмом кнута-пратта-мориса-ривеста-тарьяна. Кажется, но я их найти не могу, так что я какие-то фамилии напутал, но помню, что там было 5 великих информатиков.

    На практике же это не применяют, потому что этот алгоритм хоть и имеет линейную сложность в худшем, константа там такая, что там на квадрат хватит и еще на логарифм сверху останется. Просто используя какие-нибудь случайные числа можно добиться гораздо лочшей производительности.
    Ответ написан
    Комментировать
  • Какой мак мини взять - на интеле 2018 или M2?

    SignFinder
    @SignFinder
    Wintel\Unix Engineer\DevOps
    Если ограничений м1 по софту и т.п. нет, т весь нужный вам софт есть под arm - надо брать его. Работает быстрее интела, не лагает.
    И так как свежее, вероятно дольше будет обновляться.
    Ответ написан
  • Что делать если клиент не отдает деньги?

    an-tar
    @an-tar
    Full stack web developer
    А чем мотивирует задержку клиент?
    Все варианты возможны - ограничьте доступ, сделайте бекап, если выплаты были обещаны много ранее через полгода. В суде вряд ли что-то удастся доказать, или это будет долго и муторно. Вам урок - документы нужны, вот как раз для такого случая.
    Решать вам, по ситуации и контексту, мы тут всех нюансов не знаем.
    Ответ написан
    4 комментария
  • Используется ли двухканальный режим оперативной памяти внутри VirtualBox?

    @Drno
    Он используется на хосте.
    А виртуалка уже юзает то, что используется на хосте
    Ответ написан
    Комментировать
  • Из-за чего программа C++ на amd работает быстрее чем на intel?

    VoidVolker
    @VoidVolker
    Dark side eye. А у нас печеньки! А у вас?
    Из-за того, что процессоры от разных производителей обладают разной производительностью, внезапно, из-за отличий в архитектуре, командах, транзисторах, частотах, кэшах и во всём остальном. Сюрприз! А еще есть такие факторы как: кэши, оперативная память, дисковая подсистема, запущенные приложения, сервисы, разные ОС, разные чипсеты, разные биосы, да даже вентилятор на процессоре может влиять на производительность, из-за которого турбобуст какой-нибудь включится или выключится, и еще целый вагон других факторов.
    Ответ написан
    5 комментариев
  • Где ошибка в доказательстве?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Доказательство не верно из-за индуктивного перехода. Вы рассматриваете только уже отсортированные наборы задач. Не ясно, что добавляя задачи в другом порядке вы получаете варианты не лучше. Вы так же не показали, что вот эти 2 варианта дают оптимальное время для k+1 задачи.

    Правильное доказательство весьма простое и без индукции. Общее время будет
    Max(sum{i-начальнику}(bi), max{i - подчиненным}(ai))
    .
    Отсюда видно, что если вы какую-то задачу дали подчиненному, то все задачи с меньшим A нет смысла давать начальнику. Ведь второе слагаемое-максимум от этого не изменится, но первое увеличится. Можно "бесплатно" выполнить эти задачи подчиненными. Поэтому в оптимальном ответе вы даете какое-то множетсво минимальных A подчиненым, а остальные начальнику. Иначе можно какие-то задачи перекинуть с начальника на подчиненного и уменьшить первое слагаемое не меняя второе, уменьшив таким образом ответ, т.е. в этом случае решение точно не оптимальное.
    Чтобы все варианты возможных оптимумов перебрать надо отсортировать задачи по возрастанию A. Это код и делает. поддерживается сумма B у всех оставшихся задач, а от текущей берется A - который и будет максимумом для всех задач с меньшим A.
    Ответ написан
    Комментировать
  • Существуют ли эталонно красиво написанные программы?

    pindschik
    @pindschik
    ФЫВА ОЛДЖ
    да, их две:

    10 print "Hello world!"

    и еще:

    program HelloWorld;
    begin
    writeln('Hello World!');
    end.

    Не уверен, что можно считать эталонами варианты на С или других языках в принципе :)
    Ответ написан
    1 комментарий
  • Существуют ли эталонно красиво написанные программы?

    @Everything_is_bad
    Беда в том, что довольно трудно найти хорошо написанный код, который можно было обозреть целиком.
    бесполезное занятие, больше похоже на прокрастинацию, короче пока сам не начнешь понимать какой код "красивый", какой нет (а это только когда сам напишешь кучу кода), толку от рассматривания не будет.
    Ответ написан
    Комментировать
  • Какая сложность у этого алгоритма?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Цикл while же выполняется пропорционально количеству цифр в числе..
    Да. А количество цифр в числе C это ⌊log10C⌋ + 1.
    Элемент суммы с меньшей степенью (1) отбрасываем, округление вниз убираем, основание логарифма неважно, получаем logC
    Ответ написан
    6 комментариев
  • Обеспечивает ли HTTPS полное шифрование и невозможность компрометации данных?

    CityCat4
    @CityCat4 Куратор тега Информационная безопасность
    //COPY01 EXEC PGM=IEBGENER
    В HTTPS условно невозможны атаки типа MITM

    С х.. ли баня-то сгорела? В https атаки типа MitM цветут пышным цветом и даже не всегда считаются атаками. Например, берем корпоративный прокси с бампингом. Он выполняет, фактически именно MitM - установив тебе свой корневой сертификат, он "на лету" подменяет целевой сертификат своим, получает shared secret и спокойно себе расшифровывает соединение.
    То же самое весьма скоро будет у нас всех на компах - когда всех обязуют поставить госсертификат, без которого в тырнет просто не выйдешь.
    мы в любом случае чувствуем себя небезопасно и неаноимно

    Мы - это кто? Даже если провайдер (РКН, тащмайор) умудрится как-то узнать, что я смотрю порнуху - мне это в общем-то поуху. А политоту я в тырнет не тащу - ученый...
    но сами данные никто увидеть не сможет?

    Кроме самих даных есть еще множество косвенной информации, по которой можно достаточно точно судить о том, что "внутри". Кстати, защита некоторых протоколов на этом и базируется - убедить, что "внутри" безобидный https с котиками.
    как тогда это стыкуется с безопасностью и шифрованием данных в HTTPS, если DPI может блочить по контенту?

    на основе предположений. Например:
    1. Вася каждый день ходит на сайт 1.2.3.45 и прокачивает стопицот метров трафика
    2. На сайте 1.2.3.45 отвечает простейший сайт с котиками, который не в состоянии генерить такой трафик
    Вывод: сайт 1.2.3.45 - VPN, а сайт с котиками - заглушка, Васю вызвать на беседу.
    Ответ написан
    Комментировать
  • Ошибка Mac os Sonoma?

    GavriKos
    @GavriKos
    open core

    вот в этом.
    Ответ написан
    2 комментария
  • Ошибка unterminated string literal?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Кавычек закрывающих нет.
    Ответ написан
    Комментировать
  • Как открыть флешку в терминале линукса?

    Shoto1
    @Shoto1
    Примонтировать блочное устройство можно, например так:
    sudo mount /dev/sdb /mnt
    Ответ написан
    Комментировать
  • Можно ли сравнить большие массивы по частям?

    trapwalker
    @trapwalker
    Программист, энтузиаст
    А зачем вам это делать частями? Что вы хотите этим добиться?
    Ваша задача имеет сложность О(N) и не представляет никакой сложности, просто двигайтесь двумя курсорами синхронно по массивам и всё.
    Ответ написан
    4 комментария
  • Имеют ли силу иски о нарушении патентного права со стороны США (у них международный патент) на территории РФ?

    @other_letter
    Так а Вы на свой патент подайте. Выдадут - ОК, с Вас взятки гладки.

    А если по самому вопросу: патент действует, просто скорее всего на территории РФ его никто не будет защищать. Суд в США даже без Вроде бы с прошлого или позапрошлого года не могут принимать иски против Василия Пуканова из г. Сызрань (упрощаю специально, я понимаю, что он может быть американцем и/или владеть юрлицом на территории США или хотя бы просто получить что-то в собственность хотя бы косвенно по причине нарушения патентного права).

    Другой вопрос, что с формальной точки зрения патентное право-то не отменено само по себе. Короче, почему бы не получит ьсвой патент, а?
    Ответ написан
    2 комментария
  • Как намекнуть начальству, что agile не избавляет от тз?

    dapi
    @dapi
    Добрый день!

    27 лет в разработке IT. Исполнял роль разработчика, техлида, архитектора, владельца продукта, техдира, владельца бизнеса. Отвечу из своего опыта.

    > Как дать начальству понять, что они могут хоть 100 jira себе установить, хоть 200 совещаний в день провести, но им всё равно нужно самостоятельно планировать работу и отвечать за неё?

    1. Подготовить презентацию. Главное сконцентрироваться не на том что "так не пойдет", а на том что вы предлагаете. Покажите проблему и ваше решение. Отсюда будет видно насколько вы понимаете суть проблемы которую начальство пытается решить и поделитесь вашим предложением. Не отчаивайтесь если его не примут сразу или не примут вообще, это нормально. Если вы покажете что понимаете суть проблемы, готовые взяться за ее решение и у вас есть понятный план, то ваши шансы достаточно велики. Под проблемой я имею виду то что "100 jira не приводит к решению задач"
    2. Планировать работу самостоятельно, делегировать или не планировать, это руководство решит само. Я как руководитель вполне могу вообще ничего не планировать, а только убедиться в том что моя идея и цель донесена и понята соответствующими лицами и дальше мониторить происходящее. Например если я хочу чтобы мои подчиненные выросли и научились самостоятельно планировать.
    3. Начальство в любом случае отвечает за работу и ее результаты. Но у него есть разные рычаги как влиять на результат. Один из рычагов это сменить исполнителей.
    4. Если считаете что начальство не выполняет свои функции, скажите ему об этом (пункт 1) если вы считаете что ничего не изменилось эскалируйте вопрос далее (к начальству начальства). Для начала выясните какие функции у вашего начальства. Вполне возможно что в вашей компании составление ТЗ это функция разработчика (и это нормально).

    > Они почему-то думают, что, когда загоняешь разрабов в тасктрекер, то они сами себе будут ставить задачи и сами их выполнять, магическим образом создавать нужный (но неизвестный и не спланированный) продукт.

    Понимаю вас )

    > А чтобы корректировать курс, почему-то проводят кучу совещаний, вместо минимального тз или тупо списка требований.

    Возьмите на себя составление ТЗ. Научитесь это делать. Это поможет вам вырости как профессионал. Даже если к вам пришли с готовым ТЗ вам, для начала, нужно его принять. А именно: убедиться что выявлены все заинтересованные лица, пройтись по функциональным и не функциональным требованиям и так далее.

    Это беспроигрышный шаг которые вас поднимает на ступеньку выше в профессиональном плане.
    Ответ написан
    Комментировать
  • Почему паралельная сортировка слиянием выполняется на cpu быстрее чем на gpu в 100 раз?

    freeExec
    @freeExec
    Участник OpenStreetMap
    Выигрыш на GPU будет если нужно перемалывать гигабайты за один вызов. А на массивах в тысячу элементах ты теряешь больше времени на копирование в GPU и обратно, и на запуск ядра. И это не говоря о том, что код для GPU надо писать так, чтобы в шину уместились все данные нужные на данной итерации, а у тебя выходит, что первому потоку нужен 0 элемент, а второму не второй элемент, который бы закешировался при запросе, а тысячный. В итоге мы получаем нужные данные, не за один запрос, а за 32 (ну или столько там потоков в варпе).
    Ответ написан
    Комментировать
  • С чего начать изучать алгоритмы и структуры данных?

    AshBlade
    @AshBlade
    Просто хочу быть счастливым
    Можешь почитать "Алгоритмы. Руководство по разработке". Сам читал, база нормальная.
    Но то, о чем ты сказал (разбивать задачи на подзадачи и т.д.) - это называется "научиться мыслить аналитически". Этому нельзя научиться читая книжки - только через опыт получаешь насмотренность и набиваешь шишки. Поэтому одновременно с книгой/курсом решай задачи на условном литкоде.

    P.S. я считаю что математика нужна, т.к. она и позволяет получить вот это аналитическое мышление через призму функций, мат. абстракций, которые после переносятся на базовые конструкции ЯП (функции, переменные)
    Ответ написан
    1 комментарий
  • Какая отрасль программирования занимается анализом видео и картинок машин с дорог(штрафы ставит)?

    2ord
    @2ord
    Область компьютерного зрения и обработки изображений.
    Ищи: road traffic monitoring. один из примеров

    штрафы ставит
    Полагаю, что это комплекс различных независимых систем с интеграцией виде модулей или по API. Одна мониторит и посылает определенные события. Другая на них реагирует, агрегирует и пр.
    Ответ написан
    Комментировать