單機(jī)半在線排序算法競(jìng)爭(zhēng)比分析.pdf

1、排序算法的競(jìng)爭(zhēng)比分析是排序問(wèn)題對(duì)算法風(fēng)險(xiǎn)的一種評(píng)估和保障，具有重要的理論意義和實(shí)用價(jià)值。在排序問(wèn)題中，半在線排序所需的信息介于完全在線和完全離線的排序之間，比較符合實(shí)際應(yīng)用中的情況。近幾十年來(lái)，其研究得到了一定進(jìn)展，形形色色的半在線排序問(wèn)題和算法不斷涌現(xiàn)，但對(duì)于這些問(wèn)題算法的競(jìng)爭(zhēng)比分析幾乎處于空白。本文在經(jīng)典在線排序模型的基礎(chǔ)上，通過(guò)增加額外信息構(gòu)成半在線排序問(wèn)題，借助一般在線算法性能分析的手段和方法，通過(guò)特有的實(shí)例轉(zhuǎn)換和分析，對(duì)單機(jī)最

2、小化完工時(shí)間問(wèn)題、最小化加權(quán)完工時(shí)間問(wèn)題和最小化折扣加權(quán)完工時(shí)間問(wèn)題的半在線排序算法的性能進(jìn)行了理論分析。首先，通過(guò)構(gòu)造極端最差實(shí)例的方法，分別得到了三種半在線排序問(wèn)題的競(jìng)爭(zhēng)比下界，從而確定了半在線排序算法針對(duì)這三種問(wèn)題所能達(dá)到的性能極限。然后，對(duì)最小化完工時(shí)間證明了算法性能隨著實(shí)例空間的縮小而提升；對(duì)最小化加權(quán)完工時(shí)間問(wèn)題，分析了哪些信息有助于改善算法性能；針對(duì)最小化折扣加權(quán)完工時(shí)間問(wèn)題，設(shè)計(jì)了一個(gè)半在線排序算法，推導(dǎo)出該算法的競(jìng)爭(zhēng)比

3、，證明了該算法在三類特殊的極限情況下是最優(yōu)算法。本文的主要研究成果包括：1)對(duì)基于經(jīng)典在線排序問(wèn)題1| rj |？ Cj的半在線排序問(wèn)題完善了一種半在線排序算法競(jìng)爭(zhēng)比分析的證明過(guò)程，通過(guò)限制實(shí)例空間，證明了隨著實(shí)例空間的減小，算法性能會(huì)進(jìn)一步提高。2)針對(duì)經(jīng)典在線問(wèn)題，研究了該問(wèn)題在已知未來(lái)多步到達(dá)時(shí)間，加工時(shí)間具有上下界限制，以及兩者情況皆已知條件下任意半在線算法的競(jìng)爭(zhēng)比下界。證明了未來(lái)多步到達(dá)時(shí)間對(duì)競(jìng)爭(zhēng)比下界沒(méi)有改善，但是加工時(shí)間限