Савватеев решает задачи с собеседований. Матрица. Авто на шоссе. / ЛОГИКА САВВАТЕЕВА / ДЕПЛОЙ ПОЛЬЗА 

И звук гуляет по уровням (((

Это бета-версия

Согласен, это огромное упущение

и ноут зарядить забыли

Вы видимо сами не it) в it во первых решение задачи должно решать задачу но не обязано превосходить её) то есть если не было цели показать каракули савватеева то зачем? А во вторых не каждый it умеет настраивать цифровую технику)

Он менее эффективен, чем тот вариант на 10 страниц. Но он быстрее построчного бинарного поиска и, при этом, проще. Очень хороший баланс простоты и эффективности

Ага

Это не его планшет, и это задача организаторов съёмки - подготовить условия и аппаратуру. А так он наверно и микрофон может сам настроить, фильтр с собой принести, лампы для правильного освещения тоже с собой...

Мне кажется это не очень сложно с небольшими числами

Нет никакого О(n + m). Всегда это записывается в виде O(n), либо O(n^2)

У тебя в общем случае разное количество строк и столбцов и эти величины не зависят друг от друга

@@kirillpetrenko55 почитай про нотацию О-большое и больше не пиши такую ерунду. Там нет ни сложений, ни умножений. Есть n, 1, степени, логарифмы, факториалы

@@sergeygamer1455 хорошо))) Какова сложность алгоритма поэлементного обхода двумерного массива у которого n строк и m столбцов?

@@sergeygamer1455 какова сложность алгоритма, который суммирует все элементы матрицы размера n*m, находящиеся на ее "периметре" (1 и n строка и 1 и m столбец)? Какова сложность алгоритма, который пишет n раз "Hello", а потом m раз "World"?

понятно, что на такое собеседование лучше не ходить

Потому что бинарный поиск работает только по одному измерению. Но другое дело, что в данном случае матрицу, наверное, можно определённой перестановкой элементов свести к вектору и получить log(m*n).

У вас 80 будет стоять после 85 и т.д.

Бинарным поиском можно logN+LogM.

нет не лучше, логарифм быстрее чем линия, есть решение O(logn+logm)

@@xxxxPomaHxxxx решение O(log n + log m) не видел, я имел ввиду что O(n + m) быстрее чем O(n log m)

лол, дурачок, логарифм быстрее чем линейное время. По твоей ущербной логике если O(n log m) - логарифмическая сложность, то тогда О(n*m) - получается линейная)))

@@nicholasspezza9449 хорошо, посчитай что больше миллион плюс миллион или миллион умножить на логарифм миллиона

Не будет логарифмическая. Похоже, что линейная от n для матрицы (n*n).

Беда в том, что если из четырёх всегда остаются две четвертинки-кандидата, то их количество растёт экспоненциально по основанию 2. Показатель степени - логарифм n по основанию 2. В итоге сложность линейная.

неа)

Так это задача с собеседования, там вопрос не в формальном ответе, а в продемонстрированных навыках. Вам скажут: спасибо, до свидания.

Крч, вероятность что за 30 минут проедет авто = 95%, значит вероятность что авто не проедет = 5%. (Или 0,05) Итак за первые 10 минут вероятность, что авто не появится Х, за вторые 10 минут Х^2, за третьи 10 минут Х^3. т.к события равновероятны, то вероятности перемножаются. Нужно извлечь куб из 5%. Это 5/100 или 1/20. В ходе вычислений получаем, что кубический корень из 20 ≈ 2,7 а следовательно кубический корень из 1/20 = 1/2,7 = 0,37. Итак вероятность того, что авто не появится за 10 минут 0,37. Значит вероятность того что появится 1-0,37 = 0,63.

"т.к. события равновероятны, то вероятности перемножаются" - не равновероятны, а - зависимые. Независимые вероятности складываются, а зависимые - перемножаются. Тут их равность не играет роли, но думаю ты просто опечатался. Поправил, дабы никто случайно не ввелся в заблуждение)) @@hubertjf9726

Можно подробнее? Нужно найти 55. Начинаем справа сверху - 85, оно больше искомого, но слева нужно значения нет

@@user-wo4pr7vj2b начинаем справа сверху и если искомое число больше, то идете вниз по матрице, если меньше то влево. Например ищем 55. попали на 85. 85 больше чем 55? Да. Значит смотреть ниже 85 нет смысла, так как они отсортированы и ниже будут числа больше 85. Значит двигаемся влево на число 40, снова сравниваем 55 и 40. 55 больше, смотреть левее нет смысла, ибо они отсортированы и слева числа меньше 40, значит двигаемся на единичку вниз на число 80. Снова 55 больше 80, нет. Значит идем влево на число 35. Сравниваем 55 и 35, 55 больше значит идем вниз. И нашли.

@@alexey1930 благодарю, не так понял сначала!

поставь вместо 55 число 54, а вместо например 85 число 55. И ищи 55. Твой алгоритм тупо не найдет число. Мы не можем быть уверены, что нашли сразу столбец с числом. (ну может я не правильно понял твою идею, но вряд ли)

Нет не находим. В первом столбце 55 быть точно не может, а во всех остальных судя только по нижниму ряду может

ммм когда слушаю объяснение Савватеева - понимаю красоту и логичность его рассуждения... но найти ошибки у себя не могу. Хотя цифры выходят разные. Возможно, ошибка моя в правильном моделировании. Но чем моя формулировка отличается от оригинальной? Разве вероятность, что в течение 10 минут пройдёт машина и вероятность, что именно в ЭТИ 10 минут пройдет машина не одно и то же? Или если мы точно знаем, что в течение 30 минут пройдет автомобиль, разве суть задачи не сводится к тому, чтобы найти вероятность, что автомобиль из этих 30 минут НЕ пройдет в конкретно ЭТИ 10 минут? И если сводится, то разве данная вероятность при вышеупомянутом допущении не равна 2/3?

@@romanapanovich5267 Она не равна 2/3, потому что может приехать больше одного автобуса. Вообще говоря задача не корректна, так как под условие подходит много разных вероятностных пространств. Ваш вариант ответа тоже имеет место быть. Например если автобус в начале дня выезжает в 0, 10 или 20 минут равновероятно, приезжает каждые 30 минут, но с вероятностью 5% пропускает очередной раз. Ответ Саватеева тоже имеет место быть, если предположить что вероятность прибытия автобуса в отрезки времени равной длины одинаковы и независимы в совокупности (если отрезки не пересекаются). Тогда для любого отрезка времени длиной в 10 мин рассмотрим еще 2 рядом. Если вероятность прибытия автобуса в один из отрезков p, то и в остальные тоже p в силу равновероятности. Тогда вероятность неприбытия во все три отрезка (1-p)^3 (в силу независимости). Тогда 1 - (1 - p)^3 = 0.95 => p = 1 - 0.05^(1/3) =~ 0.63.

Спасибо за твой комментарий, читая его, я осознал, что привести правильное решение - это ещё не показатель глубокого понимания его сути и сути темы в целом. А вот опровергнуть любое неверное решение, это уже другой уровень. Пытаясь понять, где же у тебя ошибка - я окунулся глубже в теорию вероятности. Не то чтобы я теперь всё отлично понимаю, но стало ясно, что есть куда копать... Насчет твоих рассуждений - 2\3 это уже кажется ошибка, для простоты обозначим вероятность того, что автобус приехал , как "1", а того, что не приехал, как "0", тогда у нас возможны всего 6 сценариев: 1-0-0 , 1-1-0, 1-0-1, 0-1-0, 0-1-1, 0-0-1 , и уже тут ясно, что если даже рассматривать эти варианты как равновероятные, то вероятность того, что он не вышел в первой десятке - 1\2 , но на самом деле это не так, т.к. вероятность того, что автобус приедет - больше вероятности того, что он не приедет, а значит случаи, когда автобус приехал в двух разных десятках сразу будут встречаться чаще, чем случаи когда автобус приехал только в одной из трех десяток. Итого наша вероятность будет зависеть от соотношения вероятностей того, приедет автобус за 10 минут или нет, а это нам неизвестно. По очень извилистому пути ты пошел конечно, но это хорошо. Насчет рассуждений про 0,05 и 100% вероятность - я до сих пор не могу понять, корректны они или нет, точнее больше склоняюсь к тому, что некорректны, но до конца не понимаю почему. Есть над чем подумать. Дебри конечно те ещё выходят, но только так наверное и можно начать по настоящему понимать теорию вероятностей, а не просто действуя по типичным алгоритмам, которые 50\50 понял\запомнил.

Это означает только то, что мы выбрали неэффективный способ обхода.

А представьте, что у вас не квадратная матрица. Например, 1000000x1. Это уже контрпример к вашему утверждению.

@@vadimrumyantsev8498 Нет, не контрпример. Мой аргумент заключается в том, что меньше, чем за min(m,n) нельзя. А логарифм в общем случае меньше, чем min(m,n), поэтому за логарифм не получится. Для матрицы 1000000x1, min(m,n)=1. Поэтому это не противоречит моему утверждению. Хоть для такой матрицы задача решается за одно обращение, не существует алгоритма, который бы решал задачу за логарифм для *любой* матрицы.

@@vadimrumyantsev8498 Нет, это верно для любого способа. Не существует алгоритма, который ищет в неотсортированном массиве нужный элемент гарантировано за логарифм сравнений. Потому что, пока мы не сравним его со всеми, мы не можем гарантировать, что найденный элемент средний. Значит нам нужно прочитать n элементов вне зависимости от способа обхода. Поэтому в квадратной матрице, мы не найдем элемент, даже если мы точно знаем, что он на диагонали. Уж тем более мы не можем найти элемент, если мы не знаем, что он на диагонали.

@@papalyosha савватеев предложил решение за логарифм для любой матрицы. Выбрав число в середине матрицы и сравнив с ним искомое, мы выкидываем либо верхний левый, либо нижний правый квадрат. Далее повторяем эту процедуру рекурсивно для Г-образных оставшихся полей, которые разбиваются на прямоугольник и квадрат. В среднем за шаг мы будем откидывать не менее 1/8 клеток, что даёт логарифм по основанию 8/7. То, что вторая диагональ матрицы не упорядочена, ничего не значит.

расскажите?)

летит попугай и залетает пипиркой те в рот.

​@@nicholasspezza9449и дальше? Не гуглится

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

Здесь второй и третий столбик не отсортированы, поэтому и матрица.

@@cf8253 а если бы были отсортированы столбцы, то НЕ матрица?)

@@cf8253 Напиши как отсортировать её, какой результат? Во время сортировки можно вообще все элементы куда хочешь двигать что ле?

По определению: матрица отсортирована, если все её строки и все столбцы отсортированы. То есть это характеристика конкретной матрицы. Если мы хотим отсортировать некоторую матрицу, то нужно сперва определить операции, после выполнения которых будет получаться матрица, в некотором смысле эквивалентная исходной. (Как, например, при вычислении определителя: при транспонировании матрицы определитель не меняется.) Если элементы двигать как угодно, то все матрицы, содержащие одинаковые наборы чисел, будут для нас эквивалентны относительно такой сортировки.

Это решение за m+n шагов, неэффективное. Савватеев предложил log(m)*log(n). Идея тут в том, что в отсортированных последовательностях нам нет необходимости просматривать все элементы. Искать в отсортированном массиве за линейное время - это серьёзный косяк с профессиональной точки зрения, который прямо бросается в глаза. Для школы, конечно, нормально, но Савватеев понимает, что это заведомо плохой алгоритм, и поэтому не стал его рассматривать, хотя он очевиден. Например, при m=1000000 и n=1 Савватеев решит задачу за 20 шагов, а вы за 500000. Хотя его алгоритм не самый лучший.

@@vadimrumyantsev8498 Это решение действительно за O(n + m), только оно не верное. Саватеев "предложил" решение за O(log(max(n, m)), что невозможно. Вы "предлагаете" алгоритм за log(m)*log(n), что тоже не возможно. При этом говорите что линейное время - серьезный косяк, хотя очевидно что алгоритма быстрее не существует (для n = m). Забавно получается.

С житейской точки зрения кажется, что вероятность меньше, на самом деле нет. Приведу классический пример с монетами, какова вероятность выпадения решка, если перед этим подряд выпало 10 орлов, монета идеально сбалансирована? Ответ 0,5 предыдущие результаты выпадения монеты не влияют на следующие

вы человек, который не знает вероятности

@@user-ts6uy2xc8u он имел ввиду вкупе, а не отдельный результат, какова вероятность выпадения 10 орлов и решки?

​@@TtopYyyt-tm5ffтак это уже за 20 минут

нет, не X^3 = 1-0.95, а 0.05=(1-X)^3

@@lilbutcher2338 Приветствую! Что значит нет? Какие трудности в записи X^3 = 1-0.95?