Сложность алгоритмов Гаусса и Крамера решения СЛАУ

Norby · Регистрация: 12.03.2008

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

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

@alex_x_x · 21.03.2010, 23:04

ответа прямо не знаю, но раз у тебя он есть, то можно прикинуть
сложность оценивают в колве операций умножений/сложений, соответственно для метода гаусса матрицы размерности n надо посмотреть сколько умножений сложений происходит при прямом, обратном ходе
в методе крамера подобным же образом надо определить сложность вычисления n определителей величины nxn

Norby · 21.03.2010, 23:18 **[ТС]**

Ну вот для Гаусса я нашел O(n^3). А вот откуда это число взялось непонятно.

@Валерий Герасим · 04.05.2016, 21:01

Norby, ,Смотри,чтобы выполнить линейное преобразование над вектором нужно N операций(по размерности вектора),чтобы выполнить метод Гаусса,нужно для каждого из N строк выполнить N-1 линейных преобразований(если приводим к диагональному виду)...
Итого получаем N(строк)*N-1(линейных операций)*N(сложность каждой линейной операции)=O(N^3-N^2)=O(N^3)

@DeadPenguin · 04.05.2016, 22:01

Norby, вы как-то плохо искали

Посмотрите на псведококод метода Гаусса и вы сможете точно подсчитать число операций в нём; в любом случае, асимптотически это $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(n^3)$ - n проходов по строкам, потом ещё n и каждый раз n операций для вычитания ведущей строки. Метод Крамера - это искать определитель, а по определению определителя (да, такой вот каламбур, а телом бел) нужно n! операций. Даже самый экономный метод не посчитает определитель быстрее чем $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(n^4)$ , так что затея эта гиблая.

Norby 66 / 66 / 5 Регистрация: 12.03.2008 Сообщений: 392
		1
	Сложность алгоритмов Гаусса и Крамера решения СЛАУ 21.03.2010, 19:58. Показов 11332. Ответов 4 Метки нет (Все метки) Прошу знающих людей объяснить мне какую вычислительную сложность имеют вышеуказанные методы и почему. Поиск в инете ничего не дал, т.к. там только указана сложность, а обоснования нет. Заранее спасибо. 0

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	21.03.2010, 23:04	2
	ответа прямо не знаю, но раз у тебя он есть, то можно прикинуть сложность оценивают в колве операций умножений/сложений, соответственно для метода гаусса матрицы размерности n надо посмотреть сколько умножений сложений происходит при прямом, обратном ходе в методе крамера подобным же образом надо определить сложность вычисления n определителей величины nxn 0

Norby 66 / 66 / 5 Регистрация: 12.03.2008 Сообщений: 392
	21.03.2010, 23:18 [ТС]	3
	Ну вот для Гаусса я нашел O(n^3). А вот откуда это число взялось непонятно. 0

@Валерий Герасим 5 / 5 / 3 Регистрация: 07.07.2013 Сообщений: 122
	04.05.2016, 21:01	4
	Norby, ,Смотри,чтобы выполнить линейное преобразование над вектором нужно N операций(по размерности вектора),чтобы выполнить метод Гаусса,нужно для каждого из N строк выполнить N-1 линейных преобразований(если приводим к диагональному виду)... Итого получаем N(строк)N-1(линейных операций)N(сложность каждой линейной операции)=O(N^3-N^2)=O(N^3) 0

@DeadPenguin 66 / 66 / 31 Регистрация: 11.03.2016 Сообщений: 252
	04.05.2016, 22:01	5
	Norby, вы как-то плохо искали Посмотрите на псведококод метода Гаусса и вы сможете точно подсчитать число операций в нём; в любом случае, асимптотически это $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(n^3)$ - n проходов по строкам, потом ещё n и каждый раз n операций для вычитания ведущей строки. Метод Крамера - это искать определитель, а по определению определителя (да, такой вот каламбур, а телом бел) нужно n! операций. Даже самый экономный метод не посчитает определитель быстрее чем $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(n^4)$ , так что затея эта гиблая. 0

Опции темы