Ответы пользователя по тегу Алгоритмы
  • Как решить задачу на Поиск граничного элемента?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Если испытывать поочерёдно этажи 1, 2, 4, 8, ..., 2^K, 2^{K+1} до тех пор, пока яйцо не разобъётся, а потом уточнить значение F из промежутка 2^K..2^{K+1} бинарным поиском, количество попыток будет (2 lgF). Если слово «примерно» допускает коэффициент 2, то алгоритм подходит.

    Если в распоряжении только одно яйцо, то нет никакого другого способа, кроме как идти снизу вверх подряд, O(N).
    Если есть два яйца, первым можно идти с более грубым шагом A[1], A[2], A[3], ..., A[K], A[K+1], а вторым уточнять точное значение F из A[K]..A[K+1]. Причём шаг A[K+1]-A[K] определяет количество попыток для второго яйца, то есть суммарное количество попыток будет K+A[K+1]-A[K]. Осталось определить вид последовательности A[i], чтобы K+A[K+1]-A[K]=O(√A[K+1]).
    Собственно, чтобы достичь 2(√N), нужно первым яйцом идти с шагом (√N), то есть 1, 1+(√N), 1+2(√N), 1+3(√N), ..., а когда разобъётся на 1+(K+1)(√N), идти вторым подряд с этажа 2+K(√N).
    Ответ написан
    1 комментарий
  • Придумать метрику равномерности чтения файла?

    youngmysteriouslight
    @youngmysteriouslight
    ТК, ТТ, JS, FP, WM
    Нам даны m_i. Равномерность предполагает, что m_i ~ k * mo. ИМХО, удобнее сразу перейти к dp_i = abs(mo-p_i) — отклонению от среднего. Чем равномернее, тем ближе dp_i к нулю в среднем.

    Если мы не хотим учитывать порядок m_i, то функция равномерности должна быть симметрична по всем аргументам.
    Вы предлагаете использовать стандартное квадратичное отклонение sqrt(average(dp_i ^ 2)). simbajoe предлагает использовать average(dp_i). В общем случае можно выписать любой момент (на числа dp_i ведь можно смотреть как на выборку некоторой случайной величины) average(dp_i^t) или, приводя к той же «размерности», power(average(dp_i^t), 1/t), где t — любой натуральный параметр. std_dev соответствует t=2.

    Кстати, если f(x) монотонно строго возрастает от 0 до 1 на [0,1], то какую-бы оценку не взяли (например, std_dev), всегда можно предложить оценку равномерности f(std_dev). Поэтому и average(dp_i^t), и power(average(dp_i^t), 1/t) одновременно подходят на должности оценки равномерности. Если Вас не устраивает результат, его можно подкорректировать при помощи такой функции f(x). Например, если std_dev обычно порядка 0 — 0.3, то sqrt(std_dev) порядка 0 — 0.5, а power(std_dev, 1/4) порядка 0 — 0.7, то есть занимает почти весь диапазон обычно. У нас нет Вашей статистики, под которую Вы хотите построить метрику, поэтому попробуйте поэкспериментировать, подбирая показатель степени.

    Есть ещё одина доступная свобода — выбор способа усреднения average, то есть не ограничиваться средним арифметическим, но и другие варианты испробовать.

    Однако есть вопрос, важен ли на порядок m_i. Зависит от задачи. Статистики [0.1, 0.2, 0.2, 0.2, 0.2, 0.1] и [0.2, 0.1, 0.1, 0.2, 0.2, 0.2] должны давать один результат или разные? Важно ли, блоки нагруженные и простаивающие идут вразброс, или они сгруппированы секциями? Для чтения файла, мне кажется, это должно учитываться. Однако, если это Вам не важно, смотрите в сторону power(std_dev, 1/t).
    Ответ написан