Оценка сложности алгоритма перемножение квадратной матрицы

@Evgen8 · Регистрация: 24.05.2013

Студворк — интернет-сервис помощи студентам

Обычно один проход по одномерному массиву даст O(n).

C++
1
for (int i = 0; i < length; +i);

А что по поводу прохода по двумерному (в нашем случае квадртная матрица) ? Проход по всей матрице займет два цикла , но сложность же будет O(n) ?

C++
1
2
3
4
int mass[n][n];
 
for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) mass[i][j] = 0

Собственно перемножение матрицы 3х3, size = 3, кол-во элементов = 9 займет O(n^(3/2)) ? Первый два цикла просто проходят по каждому элементу результирующей матрицы O(n) (проходов будет size*size=9), а для каждого элемента еще обрабатывается одна строка сразу двух матриц O(n^(1/2)) (проходов будет size = 3 или elements_count^(1/2) = 9^(1/2) = 3) . Итого O(n^(1/2)*n) = O(n^3/2).

C++
1
2
3
4
5
6
7
8
9
for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            res[i][j] = 0;
            for (int k = 0; k < size; k++)
                res[i][j] += A[i][k] * B[k][j];
        }
    }

Правильно ли я все понял ?

@Shamil1 · 02.11.2017, 12:58

Под n обычно подразумевают линейный размер матрицы (количество строк или количество столбцов). Поэтому сложность получается O(n³).

@Evgen8 · 02.11.2017, 17:34 **[ТС]**

Сообщение от Shamil1

Под n обычно подразумевают линейный размер матрицы

Странно, а почему ? А для двумерного массива тогда как ? Ну, если матрица не квадртная, а прямоугольная 2х3 ? Беря не кол-во элементов матрицы, а ее размер - фактически не учитываем большую часть эелементов матрицы.

@Shamil1 · 02.11.2017, 18:35

Сообщение от Evgen8

Ну, если матрица не квадртная, а прямоугольная 2х3 ?

В определении есть "если существует такая константа". При этом не важно, чему равна эта константа. Поэтому, даже если один размер в 100 раз больше другого, всё равно O(100*n) эквивалентно O(n).

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

@Evgen8 · 03.11.2017, 01:26 **[ТС]**

Shamil1, все равно не понятно)
Почему один проход по одномерному массиву считается за O(n), а один проход по двумерному за O(n^2) ? Ведь вроде кол-во операций будет одинаковым ? На основании чего мне можно понять, что проход по двумерному массиву на порядок сложнее для программы ?

C++
1
2
3
int mass[9];
for (int i = 0; i < 9; +i)
     mass[i] = 0;

C++
1
2
3
4
int mass[3][3];
 
for (int i = 0; i < 3; ++i)
    for (int j = 0; j < 3; ++j) mass[i][j] = 0;

@Shamil1 · 03.11.2017, 10:46

Сообщение от Evgen8

На основании чего мне можно понять, что проход по двумерному массиву на порядок сложнее для программы ?

Потому что размер двумерного массива на порядок больше (относительно линейного размера массива).

Почему считают от линейного, а не от полного? Потому что обычно так удобнее. В большинстве случаев количество элементов в двумерном массиве на задаётся, а вычисляется.
Например, Вы собираетесь хранить результаты всех игр чемпионата в двумерном массиве. В условии задачи будет "10 команд", а не "90 игр".

@Mysterious Light · 03.11.2017, 13:30

Сообщение от Evgen8

Почему один проход по одномерному массиву считается за O(n), а один проход по двумерному за O(n^2) ? Ведь вроде кол-во операций будет одинаковым ? На основании чего мне можно понять, что проход по двумерному массиву на порядок сложнее для программы ?

Сравните:

C++
1
2
3
int mass[n];
for (int i = 0; i < n; ++i)
     mass[i] = 0;

C++
1
2
3
4
int mass[n][n];
for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        mass[i][j] = 0;

C++
1
2
3
4
int mass[n][n];
for (int i = 0; i < n*n; ++i) {
    mass[i/n][i%n] = 0;
}

В первом случае O(n) из-за одного цикла с n итерациями, во втором O(n^2) из-за двух циклов по n итераций каждый, в третьем O(n^2) из-за одного цикла с n^2 итерациями.

Обращаю внимание на то, что для анализа сложности алгоритма необходимо выделить характерный масштаб задачи (Shamil1 объяснял, как это обычно делается). В коде это выражается наличием внешнего параметра (n в моём коде). Если у Вас этого параметра нет, сложность Вашего алгоритма O(1). Например, Вы в своём последнем коде пишите конкретные числовые константы 3 и 9, поэтому время работы программы на конкретной машине может быть оценено сверху, а потому сложность O(1).

@Evgen8 · 03.11.2017, 19:09 **[ТС]**

мда, теоретическая информатика не мой конек. не доходит и все

Сообщение от Shamil1

Почему считают от линейного, а не от полного? Потому что обычно так удобнее.

ведь разные значения сложности получаем ? только из-за удобства ? разве такое вообще допустимо ?

C++
1
2
3
int mass[n*n];
for (int i = 0; i < n*n; ++i)
     mass[i] = 0;

C++
1
2
3
4
int mass[n][n];
for (int i = 0; i < n; ++i)
     for (int j = 0; j < n; ++j)
     mass[i][j] = 0;

Количество элементов будет одинаково, в памяти они тоже одинаково будут расположены (последовательно). Для прохода по всем элементам для двумерного массива немного сложнее будет вычислить адрес. Не просто базовый+i*4 (4 - размер int), а еще учесть размерность, формула измениться.... Вроде все похоже, но у одномерного O(n), а у двумерного O(n^2). За что ?)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int * massOne = new int[1048576];
    int ** massTwo = new int * [1024];
for (int i = 0; i < 1024; ++i) massTwo[i] = new int[1024];
 
*****
 
startTime = GetTickCount();
    for (int i = 0; i < 1048576; ++i) massOne[i] = Base::RandomInt(-5, 5);
    endTime = GetTickCount();
 
    startTime = GetTickCount();
    for (int i = 0; i < 1024; ++i)
        for (int j = 0; j < 1024; ++j) massTwo[i][j] = Base::RandomInt(-5, 5);
    endTime = GetTickCount();

Такой код выдал 3093 для одномерного, 3094 для двумерного. В среднем разница +-50 ms
Если взять матрицу 512х512 и одномерный 512^2 получим 782 и 765 (двумерный). В среднем +-20.
Хотя по картинки во вложении я должен был получить хоть какую-то разницу между проходами.

Не по теме:

p.s. такое чувство, что я что-то фундоментальное не понимаю... :-|

@Mysterious Light · 03.11.2017, 19:39

Сообщение от Evgen8

Вроде все похоже, но у одномерного O(n), а у двумерного O(n^2). За что ?

Я, между прочим, об этом только что говорил. Если у Вас один цикл в n^2 итераций, то будет O(n^2). А ещё я говорил, что для оценки сложности нужно выделить характерный размер -- n. А Shamil1 говорил, что в качестве n для массивов как правило (тем более, если не оговорено обратное) выбирают длину массива, что совсем не согласуется со строкой

Сообщение от Evgen8

C++
1
int mass[n*n];

Подведём итоги. Если есть одномерный массив с n элементами и однопроходной цикл по нему, сложность составляет O(n).
Если дан массив с n^2 элементами, сложность будет O(n^2). Если n^3, то O(n^3). Если f(n) элементов, то O(f(n)).

Добавлено через 1 минуту
P.S. а ещё таблица немножко может вводить в заблуждение: в определении сложности фигурирует константа, от которой существенно зависят не только числовые значения, но и порядки указанных величин.

Добавлено через 6 минут
хотя, если подумать, возможно, речь в таблице идёт о точной зависимости времени в условных операциях, каждая из которых требует 0,000001с.

@Shamil1 · 03.11.2017, 19:40

Сообщение от Evgen8

ведь разные значения сложности получаем ?

Вот ответ:

Сообщение от Mysterious Light

А ещё я говорил, что для оценки сложности нужно выделить характерный размер -- n.

Поясняю. Сложность - это функция от некоторого параметра. Разумеется, вид этой функции будет зависеть от выбора этого параметра.

@Evgen8 · 03.11.2017, 21:11 **[ТС]**

Ок. Насколько я понял, если я возьму за n - количество элементов матрицы, а не ее размерность, то получу O(n) за два цикла (проход по матрице). Возьму за n ее размерность, тобишь size - получу O(n^2) за один проход по ней. Но во всем мире договорились для анализа сложности двумерной матрицы брать ее размерность, а не кол-во элементов, потому что так удобней (а правильней ли это ? еще не понял). Тру мысли ?

@Shamil1 · 04.11.2017, 17:52

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

Например, задача "решить систему из n линейных уравнений с n неизвестными".
Естественно, что нас интересует зависимость от количества уравнений/неизвестных, а не от количества элементов в двумерном массиве, который мы можем использовать (а можем и не использовать) для решения данной задачи.

@pke · 17.06.2021, 11:51

Shamil1, Добрый день! Могли бы помочь в решении 2 задач.
1. Определите временную сложность О для алгоритма вычисления произведения матриц (последовательный режим). Считать матрицы квадратными размерности nn. Считать, что операции сложения и умножения занимают одинаковое время процессора.
2. Определите значения ускорения, эффективности и стоимости, если известны следующие временные характеристики: для 6-ти процессоров время выполнения последовательной части составляет 25 % и время выполнения параллельной части составляет 75 %.

@Shamil1 · 17.06.2021, 20:38

Сообщение от pke

Могли бы помочь в решении 2 задач.

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

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	02.11.2017, 12:58
	Под n обычно подразумевают линейный размер матрицы (количество строк или количество столбцов). Поэтому сложность получается O(n³). 0

@Evgen8 4 / 4 / 2 Регистрация: 24.05.2013 Сообщений: 300
	03.11.2017, 21:11 [ТС]
	Ок. Насколько я понял, если я возьму за n - количество элементов матрицы, а не ее размерность, то получу O(n) за два цикла (проход по матрице). Возьму за n ее размерность, тобишь size - получу O(n^2) за один проход по ней. Но во всем мире договорились для анализа сложности двумерной матрицы брать ее размерность, а не кол-во элементов, потому что так удобней (а правильней ли это ? еще не понял). Тру мысли ? 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	04.11.2017, 17:52
	Сообщение было отмечено Evgen8 как решение Решение Примерно так. Только не договорились, а потому что это диктуется объективной необходимостью. Нас интересует сложность в зависимости от параметров, заданных в условии задачи. Например, задача "решить систему из n линейных уравнений с n неизвестными". Естественно, что нас интересует зависимость от количества уравнений/неизвестных, а не от количества элементов в двумерном массиве, который мы можем использовать (а можем и не использовать) для решения данной задачи. 0

@pke 0 / 0 / 0 Регистрация: 17.06.2021 Сообщений: 1
	17.06.2021, 11:51
	Shamil1, Добрый день! Могли бы помочь в решении 2 задач. 1. Определите временную сложность О для алгоритма вычисления произведения матриц (последовательный режим). Считать матрицы квадратными размерности nn. Считать, что операции сложения и умножения занимают одинаковое время процессора. 2. Определите значения ускорения, эффективности и стоимости, если известны следующие временные характеристики: для 6-ти процессоров время выполнения последовательной части составляет 25 % и время выполнения параллельной части составляет 75 %. 0

Оценка сложности алгоритма перемножение квадратной матрицы

Решение