設(shè)數(shù)組A有n個元素,需要找出其中的最大最小值。
(1)請給出一個解決方法,并分析其復(fù)雜性。
(2)把n個元素等分為兩組A1和A2,分別求這兩組的最大值和最小值,然后分別將這兩組的最大值和最小值相比較,求出全部元素的最大值和最小值。如果A1和A2中的元素多于兩個,則再用上述方法各分為兩個子集。直至子集中元素至多兩個元素為止。這是什么方法的思想?請給出該方法的算法描述,并分析其復(fù)雜性。
(1)基本思想:從頭到尾逐個掃描,紀(jì)錄最大和最小元素。
輸入:具有n個元素的數(shù)組
輸出:最大值和最小值
步驟: