بسط لاپلاس

در روش بسط لاپلاس، محاسبه دترمینان یک ماتریس مرتبه 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های بزرگ کارایی ندارد.

منابع

محاسبه دترمینان ماتریس بایگانی‌شده در ۸ ژوئن ۲۰۱۲ توسط Wayback Machine