問(wèn)答題

【簡(jiǎn)答題】給定一個(gè)由n個(gè)數(shù)組成的序列，要求該序列的最長(zhǎng)單調(diào)上升子序列，請(qǐng)?jiān)O(shè)計(jì)對(duì)應(yīng)的算法并分析其時(shí)間復(fù)雜度，如果時(shí)間復(fù)雜度劣于O（nlogn）的，將其優(yōu)化為O（nlogn）時(shí)間復(fù)雜度的算法。

答案：假設(shè)當(dāng)前已求出m[1..i-1]，當(dāng)前保留的狀態(tài)集合為S，下面計(jì)算m[i]。
1、若存在狀態(tài)k∈S，...

你可能感興趣的試題

問(wèn)答題

【簡(jiǎn)答題】給定線性序集中n個(gè)元素和一個(gè)整數(shù)k，1≤k≤n，要求找出這n個(gè)元素中第k小的元素，請(qǐng)?jiān)O(shè)計(jì)一個(gè)最壞時(shí)間復(fù)雜度為O（n）的算法，并對(duì)其時(shí)間復(fù)雜度進(jìn)行分析說(shuō)明。

答案：我們把這種算法叫做快速選擇（quickselect）。令〡Si〡為Si中元素的個(gè)數(shù)，快速選擇的步驟如下：
1）...

問(wèn)答題

【簡(jiǎn)答題】有4個(gè)矩陣{A₁，A₂，A₃，A₄}，其中Ai與A_i＋1是可乘的，i=1，2，3，連乘積為A₁A₂A₃A₄。在這個(gè)四矩陣連乘積問(wèn)題中，請(qǐng)問(wèn)不同子問(wèn)題的個(gè)數(shù)總共有多少個(gè)，并請(qǐng)把所有的子問(wèn)題列出來(lái)。

答案： 5個(gè)
（A1（A2（A3A4）））
（A1（（A2A3）A4））
（（A1A2）（A3A4...

<label id="bhq3r"><xmp id="bhq3r">

<label id="bhq3r"></label>

<span id="bhq3r"></span>