Skip to content

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

Notifications You must be signed in to change notification settings

wmurw/determinant

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

11 Commits
 
 
 
 

Repository files navigation

determinant (определитель матрицы)

Классический алгоритм вычисления определителя матрицы с помощью миноров и рекурсии. Как ни странно, все виденные мною реализации этого алгоритма на каждом вызове рекурсии создают новую матрицу и копируют в неё минор. В то время, как совершенно ничего не мешает получать минор, используя указатели на исходную матрицу. Это уменьшает затраты и памяти, и машинного времени. Правда вычисление определителя через миноры изначально алгоритмически не эффективно, возможно поэтому никто кроме студентов его не использует и некому думать над его оптимизацией. Количество операций в этом алгоритме пропорционально факториалу размера матрицы, а это очень быстрорастущая функция, поэтому использовать алгоритм для больших матриц принципиально невозможно. Из-за этого практическая ценность этого алгоритма весьма невысока, по сути он пригоден только для учебных целей, чтобы на практике разобраться в сути вопроса. Тем не менее, приведу здесь версию с указателями, без выделения лишней памяти и копирования миноров. Может кому и пригодится в поисках просветления. А для практического вычисления определителей стоит использовать метод Гауса - он не имеет таких жёстких ограничений на размер матрицы.

About

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

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages