بسط لاپلاس
در روش بسط لاپلاس، محاسبه دترمینان یک ماتریس مرتبه n، به محاسبه دترمینان n ماتریس کهاد از مرتبه n - 1 شکسته میشود.
پیچیدگی زمانی بسط لاپلاس
اگر عمل اصلی محاسبات را اعمال ضرب و جمع در نظر گرفته، و ( T1( n تعداد این اعمال را برای محاسبه دترمینان ماتریس مرتبه n به روش بسط لاپلاس نشان دهد، میتوان نوشت:
T1( n ) = n T1( n - 1 ) + n + n + n - 1 = n T1( n - 1 ) + 3n - 1 , T1( 1 ) = 0
( n T1( n - 1: تعداد اعمال لازم برای محاسبه زیر مسائل n: تعداد ضربهای بین aij و توانهای زوج یا فرد منفی یک
n: تعداد ضربهای بین aij و ( det( Aij
n - 1: تعداد جمعهای لازم برای محاسبه نهایی
حل این رابطه بازگشتی نشان میدهد که ( T1( n از مرتبه ( !O( n است، که برای nهای بزرگ کارایی ندارد.
منابع
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.