حل تشریحی سوال شماره 32 دروس مشترک (ساختمان‌های گسسته، ساختمان داده‌ها، طراحی الگوریتم، مهندسی نرم‌افزار، شبکه‌های کامپیوتری)

چند مورد از عبارات زیر، برای محاسبه زیر دنباله صعودی از یک دنباله دلخواه A به طول n، درست است؟

• یک راه حل پویا با مرتبه زمانی $O\left(n^2\right)$ و میزان حافظه کمکی $O\left(n^2\right)$ ، برای آن وجود دارد.
• یک راه حل سریع در مرتبه (nlogn)O و با الگوریتمی که از الگوریتم جستجوی دودویی استفاده می کند، ممکن خواهد بود.
• دنباله A را مرتب میکنیم و آن را $A^{\prime }$ می نامیم سپس بزرگترین دنباله مشترک بین A و $A^{\prime }$ را محاسبه می کنیم.
• تعداد زیر دنباله های صعودی به طول از A از رابطه $T\left(n\right)={\sum }_{i=1}^{n-1}T\left(k\right)T\left(n-k\right)$ به دست می آید.