Как определить сложность алгоритма?

[Bloomberg]

Проходя курс линейной алгебры мне стало скучно и я написал скриптик, который находит определитель матриц.

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

Вопрос: как вычислить, что лучше - находить определитель в тупую, или всё же искать возможности (находить по другой строке/столбцу, приводить к нулям и т.д.). Я про time complexity слышал только мельком, не уверен, куда копать дальше.

На всякий случай - код:

Используется синтаксис Javascript

function calcDeterminant(matrix) {
        var matrixLength = matrix.length;
        if (matrixLength > 2) {
                var determinant = 0;
                for (var i = 0; i < matrixLength; i++) {
                        var minor = calcMinor(matrix, i);
                        determinant += matrix[0][i] * Math.pow(-1, 1 + (i + 1)) * calcDeterminant(minor);
                }
                return determinant;

        } else {
                return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
        }
}

function calcMinor(matrix, delIndex) {
        var minor = [];
        matrix = matrix.slice(0);
        matrix.shift();

        var matrixLength = matrix.length;
        for (var i = 0; i < matrixLength; i++) {
                minor.push(matrix[i].filter(function(val, index) {
                        return index !== delIndex;
                }));
        }

        return minor;

 

[mustitz]

Ну а попробуй вычислить определитель единичной матрицы 10-го порядка твоим скриптом.

Просто посчитайте, сколько умножений потребует твой алгоритм. Итак, при $n=2$ получаем два умножения. $K_2 = 2$. При $n=3$ получаем два умножения в цикле из трех итераций плюс $K_2$ умножений при рекурсивном вызове, получим $K_3=2 \cdot 3 \cdot K_2$. Чему равно $K_n$?

[arseniiv]

Bloomberg, обычно в ситуациях, когда пригождается определитель $|A|$, его находят численными методами как побочный продукт какого-то другого алгоритма. Самое простое и безобразное — решить систему $A\mathbf x = \mathbf0$ методом Гаусса, после прямого хода которого произведение элементов на диагонали преобразованной матрицы даст определитель. Сложность этого по времени $O(n^3)$.

У вас сложность должна быть $O(n!)$, экспоненциальная, да и реализация не очень. Незачем создавать для вычисления минора новый массив (ладно бы память, но и на времени это тоже сказывается), вычислять целую степень $-1$ с помощью Math.pow — ээ…

-- Вт ноя 26, 2013 23:15:39 --

mustitz, простите, что не заметил вашего совета по вычислению сложности и раскрыл карты.

Bloomberg в сообщении #792967 писал(а):

или всё же искать возможности (находить по другой строке/столбцу, приводить к нулям и т.д.

Это может повлиять на численные особенности, о которых не возьмусь говорить, хотя это не менее важно, чем временная сложность. Последняя от этого не уменьшится точно. Одну временную сложность, как вы понимаете, для анализа знать мало. Особенно для алгоритмов, оперирующих floating-point числами.

Bloomberg в сообщении #792967 писал(а):

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

Не то чтобы задуматься, но, скорее, делать лишнее. Кстати, находить определители матриц выше 3-го порядка не какого-то специального вида человеку вручную не только незачем, но и вообще вредно — это значит, что он делает что-то не то. (Это моё личное мнение.)

[Bloomberg]

Спасибо.
А чем вы бы заменили Math.pow?
Насчёт минора я тоже не очень понимаю, как это сделать без другого массива (нельзя ведь просто резать один и тот же массив), если не переделывать это полностью.

[rockclimber]

Bloomberg в сообщении #793249 писал(а):

Спасибо.
А чем вы бы заменили Math.pow?

Ну если вы -1 возводите в целую степень, то, как мне кажется, должно быть очевидно, что результат будет равен 1 для четных степеней и -1 для нечетных.

[Bloomberg]

rockclimber в сообщении #793265 писал(а):

Bloomberg в сообщении #793249 писал(а):

Спасибо.
А чем вы бы заменили Math.pow?

Ну если вы -1 возводите в целую степень, то, как мне кажется, должно быть очевидно, что результат будет равен 1 для четных степеней и -1 для нечетных.

Это понятно. Я имел в виду, чем это заменить, что будет лучше в плане производительности. Вот я и спрашиваю, может я не знаю, как можно эффективно -1 в степень.

http://jsperf.com/math-powt/2

[Bloomberg]

Затупил. Да, конкретно в этом случае разницы почти нет, как возводить в степень, но само по себе ((i + 2) % 2 === 0 ? 1 : -1) быстрее в два раза.

[arseniiv]

Bloomberg в сообщении #793249 писал(а):

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

Никто не заставляет трогать массив. Что вам нужно от массива? Только индексирование. Значит, надо просто иметь способ индексировать одинаково как массив, так и массив с дырками. Например, объект хранит индексы исключённых из рассмотрения строк и столбцов и (ссылку, конечно, на — другое здесь и не получится) массив. Не знаю, есть ли в JS способ перегрузить индексирование (недавно узнал, что в нём есть свойства ); даже если нет, можно завести функцию getAt двух параметров, а ещё нужна функция определения размера. Дело будет только за эффективной реализацией getAt и, соответственно ей, способом хранения исключённых индексов.

Ещё:

• конструктор принимает исходный массив, давая его «копию» без дырок;
• есть метод получения из данной «копии» «копии» с исключёнными данной строкой и столбцом. Без него затея выглядела бы странно.

Тогда функция вычисления определителя перепишется (в неудачном случае отсутствия перегрузки индексирования) как

Используется синтаксис Javascript

function calcDeterminant(matrix) {
    if (!(matrix instanceof FancyMatrix)) {
        matrix = new FancyMatrix(matrix);
    }
    var matrixLength = matrix.length;
    if (matrixLength > 2) {
        var determinant = 0;
        for (var i = 0; i < matrixLength; i++) {
            var minor = matrix.crossOut(0, i);
            determinant += matrix.getAt(0,i) * (...) * calcDeterminant(minor);
        }
        return determinant;
    } else {
        return matrix.getAt(0, 0) * matrix.getAt(1, 1) - matrix.getAt(0, 1) * matrix.getAt(1, 0);
    }
}

(Надеюсь, код правильный. На JS почти не пишу.)

А вообще лучше всё-таки использовать методы с меньшей временной сложностью.