acm程序設(shè)計(jì)算法原理和acm入門(mén)(已修改)
2025-08-30 19:01 本頁(yè)面
【正文】 ACM程序設(shè)計(jì) 東北林業(yè)大學(xué) 陳宇 2020/9/16 2 第一講 算法原理和 ACM入門(mén) (Introduction to ACM) 2020/9/16 3 我校的 ACM在線評(píng)測(cè)系統(tǒng) ? ? 課件下載地址： ? 2020/9/16 4 開(kāi)課目的 ? 為林大 ACM代表隊(duì)培養(yǎng)后備人才 ? 提高分析問(wèn)題和應(yīng)用計(jì)算機(jī)編程解決問(wèn)題的能力 ? 培養(yǎng)必要的自學(xué)能力 ? 培養(yǎng)學(xué)生的協(xié)調(diào)和溝通能力 ? 體會(huì)學(xué)習(xí)的快樂(lè) 2020/9/16 5 ACM/ICPC in China 中國(guó)大陸高校從 1996年開(kāi)始參加 ACM/ICPC—— ? 前六屆中國(guó)賽區(qū)設(shè)在上海，由上海大學(xué)承辦； ? 2020年 ： 清華和西安交大； ? 2020年 ： 清華和中山 ； ? 2020年 ： 北大和上海交大 ； ? 2020年 ： 川大、北大和浙大 ； ? 2020年 ： 上海大學(xué)、清華和西電 ； ? 2020年：北航、南航、吉大、西華 ； ? 2020年：哈工程、北交、中科大、 杭電 、西南民大 ； ? 2020年：哈工 大 、中科大、 NIT、武大 、 東華； ? 2020年：天大、福大、川大、哈工程、浙江理工； 2020/9/16 6 ACM in NEFU ? 2020年 9月，第一次參加此類(lèi)比賽（黑龍江省賽） ? 2020～ 2020，每年 5月 —— 黑龍江省第 1～ 5屆大學(xué)生程序設(shè)計(jì)競(jìng)賽 ? 2020～ 2020，每年 6月 —— 東北地區(qū)第 1～ 4屆大學(xué)生程序設(shè)計(jì)競(jìng)賽 2020～ 2020，每年 9月 —— 11月 第 29～ 34屆 ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽亞洲區(qū)預(yù)選賽 2020/9/16 7 預(yù)期賽事（今后每年） ? 3~4月，舉行校內(nèi)大賽（暨選拔賽） ? 4月， ACM全國(guó)邀請(qǐng)賽 ? 5月，參加黑龍江省大學(xué)生程序設(shè)計(jì)大賽 ? 6月，參加?xùn)|北 4省大學(xué)生程序設(shè)計(jì)大賽 ? 10~11月，參加 ACM/ICPC亞洲區(qū)比賽（至少參加 4～5個(gè)賽區(qū) 的比賽） ? 另外，每學(xué)期至少有三次月賽以及適當(dāng)?shù)木毩?xí)賽 2020/9/16 8 2020年的風(fēng)采 2020/9/16 9 2020/9/16 10 2020/9/16 11 2020/9/16 12 2020/9/16 13 2020/9/16 14 2020/9/16 15 2020/9/16 16 2020/9/16 17 2020/9/16 18 2020/9/16 19 2020/9/16 20 2020/9/16 21 2020/9/16 22 2020/9/16 23 第一部分 算法概述 算法分析的目的： ? 設(shè)計(jì)算法 —— 設(shè)計(jì)出復(fù)雜性盡可能低的算法 ? 選擇算法 —— 在多種算法中選擇其中復(fù)雜性最低者 算法分析（ Algorithm Analysis）：對(duì)算法所需要的兩種計(jì)算機(jī)資源 —— 時(shí)間和空間進(jìn)行估算 ? 時(shí)間復(fù)雜性（ Time Complexity） ? 空間復(fù)雜性（ Space Complexity） 2020/9/16 24 評(píng)價(jià)算法 ? 評(píng)價(jià)算法的三條主要 標(biāo)準(zhǔn) 是： ? (1) 算法實(shí)現(xiàn)所耗費(fèi)的 時(shí)間 ； ? (2) 算法實(shí)現(xiàn)所所耗費(fèi)的存儲(chǔ) 空間 ，其中 ? 主要考慮輔助存儲(chǔ)空間； ? (3) 算法應(yīng)易于 理解 ，易于編碼，易于調(diào) ? 試等等。 2020/9/16 25 和算法執(zhí)行時(shí)間相關(guān)的因素 ： 1）問(wèn)題中數(shù)據(jù)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu) 2）算法采用的數(shù)學(xué)模型 3）算法設(shè)計(jì)的策略 4）問(wèn)題的規(guī)模 5）實(shí)現(xiàn)算法的程序設(shè)計(jì)語(yǔ)言 6）編譯算法產(chǎn)生的機(jī)器代碼的質(zhì)量 7）計(jì)算機(jī)執(zhí)行指令的速度 2020/9/16 26 算法效率的衡量方法 ? 通常有兩種衡量算法效率的方法 : ? 1）事后統(tǒng)計(jì)法（有缺點(diǎn)，較少使用） ? 2）事前分析估算法 ? 算法的時(shí)間效率是問(wèn)題規(guī)模的函數(shù)。假如 ,隨著問(wèn)題規(guī)模 n的增長(zhǎng) ,算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n)的增長(zhǎng)率相同 ,則可記作 :T(n)=Ο(f(n)),稱(chēng) T(n)為算法的 漸近時(shí)間復(fù)雜度 (Asymptotic Time Complexity),簡(jiǎn)稱(chēng) 時(shí)間復(fù)雜度 。 Ο是數(shù)量級(jí)的符號(hào)。 2020/9/16 27 ? 一個(gè)算法中 所有語(yǔ)句的頻度之和 構(gòu)成了該算法的運(yùn)行時(shí)間。 ? 例如： for(j=1。j=n。++j) ? for(k=1。k=n。++k) ? ++x； ? ? 語(yǔ)句“ ++x、 k=n、 ++k”的頻度是 n2， ? 語(yǔ)句“ j= k=1”的頻度是 1， ? 語(yǔ)句“ j=n。++j”的頻度是 n。 ? 算法運(yùn)行時(shí)間為： 3*n2+2n+2。 2020/9/16 28 再看看這個(gè)代碼： 對(duì)較復(fù)雜的算法計(jì)算算法的運(yùn)行時(shí)間 ,經(jīng)常從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是 基本 (或者說(shuō)是主要 ) 的原操作 ,以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則 。 這個(gè)原操作 ,多數(shù)情況下是最深層次循環(huán)體內(nèi)的語(yǔ)句中的原操作 。 例如： for(i=1。i=n。++i) for(j=1。j=n。++j) { c[i,j]=0。 for(k=0。k=n。++k) c[i,j]= c[i,j]+a[i,k]*b[k,j]。 } 2020/9/16 29 ? 當(dāng)一個(gè)算法的算法運(yùn)行時(shí)間為 n2+n+1，由于 n2+n+1與 n2的數(shù)量級(jí)相等 (該表達(dá)式當(dāng) n足夠大時(shí)約等于 n2), 我們說(shuō)這個(gè) 算法的漸進(jìn)時(shí)間復(fù)雜度 (簡(jiǎn)稱(chēng) 算法的時(shí)間復(fù)雜度 )為： T(n)=O(n2)。 2020/9/16 30 算法 (漸進(jìn) )時(shí)間復(fù)雜度 ,一般均表示為以下幾種數(shù)量級(jí)的形式 (n為問(wèn)題的規(guī)模 ,c為一常量 )： ? Ο(1)稱(chēng)為常數(shù)級(jí) ? Ο(logn)稱(chēng)為對(duì)數(shù)級(jí) ? Ο(n)稱(chēng)為線性級(jí) ? Ο(nc)稱(chēng)為多項(xiàng)式級(jí) ? Ο()稱(chēng)為指數(shù)級(jí) ? Ο(n!)稱(chēng)為階乘級(jí) 以上時(shí)間復(fù)雜度級(jí)別是由低到高排列的 ,其隨規(guī)模 n的增長(zhǎng)率見(jiàn)下圖。 2020/9/16 31 圖 T(n)與規(guī)模 n的函數(shù)關(guān)系 2020/9/16 32 ? Temp=i； i=j； j=temp； ? 以上三條單個(gè)語(yǔ)句的頻度均為 1，該算法段的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模 n無(wú)關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作 T(n)=Ο(1)。 ? 如果算法的執(zhí)行時(shí)間不隨著問(wèn)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1