mayton2019

А я вообще не понял почему автор "ударил лицом" в грязь. Разве речь шла о хакатонах или олимпиадах.

Вообще в ентерпрайзе например нет таких оценок времени. Задача которая делается за 10 минут - скорее всего никому не нужна. Задача должна быть обдумана. Покрыта тестами. Покрыта code-review.

Мой шеф говорил - "задача должна настояться". Я-бы голосовал 1 StoryPoint. Или один день разработки. А то что "подруга" решала за 5 минут - было похоже на троллинг молодого кавалера или развод на слабо. Зачем вообще вестись на такое?

Если у вас d не равно 1 тогда возникает flow который приводит к matrix которая не аллоцирована.

Кстати вы используете не матрицу а так называемый Jagged Array (зубастый массив). В этом нет смысла т.к. у вас матрица всегда прямоугольная и рациональнее выделить один большой массив и распределять его ячейки как элементы прямоугольной матрицы (i,j) формула смещения - очень простая. Ширину умножить на один индекс плюс второй.

Я-бы делал так

float* matrix = new float[n * m]
ну и формулы доступа дальше подправить надо соотвественоо.

Да. Корректно. Но если вы не пользуетесь билдером то вам придется вручную отслеживать открывающие и закрывающие скобки в тек местах где есть приоритет и вручную форматировать отступы и переносы если есть такое требование. Тоесть в какой-то момент времени сложность кодогенерации перейдет с билдера в ваш рукотворный код и вам эту сложность также придется поддерживать и объяснять ее происхождение коллегам.

Кстати на каком языке вы разрабатываете? Для Java есть готовые билдеры в QueryDSL, JooQ.

Понимать сложность алгоритмов - сложно. В общем случае глядя на исходних достаточно трудно сказать какое там o(n). Особенно если есть рекурсии и предикаты которые срабатывают с вероятностью которую мы не знаем.

Вообще, нарабатывая опыт. Например обход элементов квадратной матрицы имеет квадратичную стоимость а обход куба - кубическую. Это из простого. Шаблоны дихотомического поиска почти всегда содержат в основе своей формулы логарифм по основанию 2. И комбинаторные алгоритмы (сочетания и перестановки) - практически всегда содержат в своей основе n под факториалом.

Кстати если формула содержит суперпозицию факториала и полинома - то полином можно выкинуть. Т.к. в сравнении пределов факториал улетает в бесконечность быстрее и соотв. решение зависит только от факториала.

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

По поводу Дональда Кнута. Ничего он не поймет. Кнут писал 40 лет назад. Писал про железо которого уже не существует (ленточные накопители) и продавливал свои идеи алгоритмизации на ограниченном числе ресурсов. Кнут просто издевается над современным читателем имеющим ноутбук и смартфон тем фактом что заставляет изучать несуществующий компьютер MMIX (это такая себе машинка-калькулятор вроде Феликса или Энигмы, такие вот у меня ассоциации) и под него-же писать и читать код. Ну кому это надо!

Сегодня я снимаю шляпу перед тем трудом который он сотворил. Но если студент хочет ПРОСТО освоить тему оценок сложностей алгоритмов то можно взять что-то более быстрое и эффективное. Вирт. Седжвик. Даже Кормен.

Нормально все считается. У меня вышло

sizeof(double) = 8 bytes
z = 16.66666666666666785090

gcc version 9.4.0