Ответы пользователя по тегу Математические матрицы
  • Как определять сложность алгоритма?

    @Mercury13
    Программист на «си с крестами» и не только
    Начнём с того, что такое символы Ландау (не того, немца Эдмунда Ландау) O(f(n)) и o(f(n)) при n→∞.
    g(n) = O(f(n)), если при достаточном n g(n)≤cf(n).
    g(n) = O(f(n)), если g(n)/f(n) → 0 при стремлении n→∞.
    Таким образом…
    • Символы Ландау отражают изменение чего-то (времени, памяти и т.д.) при n→∞.
    • Если, например, два цикла друг в друге и каждый по n — пишем O(n²). Например, для умножения матриц n×n:
    для i = 1…n
      для j = 1…n
        s = 0
        для k = 1…n
          s += a[i,k]·b[k,j]
        c[i,j] = s

    Тут три вложенных друг вы друга цикла по n — так что сразу же пишем O(n³).
    • Если g(n) = O(n), то g(n) = O(n²), потому мы не грешим против истины. Но если вдруг оказалось, что внутренний цикл — это извлечение из очереди и через эту самую очередь пройдут, например, 2n событий — внешний цикл выполняется O(n) раз и внутренний O(n) раз; оценка алгоритма сразу же превращается в O(n).
    • Константы мы, разумеется, выкидываем: и 2n², и 200n² = O(n²). Также выкидываем те части, чей порядок меньше, чем самый крупный: n²+n log n = O(n²). Кстати, потому мы и не пишем основание логарифма: логарифмы разных оснований отличаются множителем.
    • Но иногда константы важны. Скоростные методы умножения матриц имеют насколько большую константу при n2,81, что реально они начинают иметь смысл где-то со 100×100 (а то и крупнее). По той же причине живёт двоичный алгоритм поиска подстроки — он имеет крайне низкую константу при n² и ещё парочку полезных свойств.
    Ответ написан
  • Что такое совпадение множеств?

    @Mercury13
    Программист на «си с крестами» и не только
    Совпадают множества — это, собственно, равны как множества. Другими словами, равны, если исключить повторы и отсортировать в каком-нибудь порядке.
    Например, { 1, 2, 3 } = { 3, 3, 2, 1, 2, 1 }.
    Ответ написан
  • Матрица поворота плоскости изображения или вектора на центр камеры относительно осей координат?

    @Mercury13
    Программист на «си с крестами» и не только
    Первое. То есть в какую сторону смотрит объектив и как он повёрнут вокруг оси.
    Второе (указатель на центр камеры) — это вектор c.
    Ответ написан
  • Как разобрать матрицу трансформации на состовляющие?

    @Mercury13
    Программист на «си с крестами» и не только
    Как я понял, твоя матрица 3×3 — это однородные координаты в 2D? Я бы поступил так.
    1. Убедиться, что элементы 3-1 и 3-2 нули (иначе — это не аффинное преобразование).
    2. Элемент 3-3 превратить в единицу, соответственно увеличив остальные (на что — читай, что такое однородные координаты).
    3. Элементы 1-3 и 2-3 — перенос. Отрежем их, получается матрица 2×2.
    4. То, что осталось, должно быть вида (c, s), (-s, c). Если с какой-то погрешностью это не так и 2-норма строк не единица (тоже с какой-то погрешностью) — это не поворот (т.е. может быть масштабирование или наклон). Остаётся взять atan2(c, s) — получается угол.
    Ответ написан