計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)[王曉東][電子教案]第1章-文庫吧資料
2024-08-22 15:33本頁面
【正文】 = log(log n)。 ? ln n = logen。 ?????????032!!3!21 iixixxxxe ?xnn enx ??????? ??? 1lim? （ 5）對(duì)數(shù)函數(shù) ? log n = log2n。 ? |x| ?1 ? 1+x ? ex ? 1+x+x2 。 ? a1 ? an為 單調(diào)遞增函數(shù) 。 ? (am)n = (an)m 。 ? a1=1/a 。 ? k d ? p(n) = ?(nk) . ? （ 4）指數(shù)函數(shù) ? 對(duì)于正整數(shù) m,n和實(shí)數(shù) a0: ? a0=1。 ? k ? d ? p(n) = ?(nk) 。 ? f(n) = O(nk) ? f(n)多項(xiàng)式有界； ? f(n) = O(1) ? f(n) ? c。 ? （ 3）多項(xiàng)式函數(shù) ? p(n)= a0+a1n+a2n2+…+ adnd； ad0。 ? ? a/b ? ? (a(b1))/b。 ? ? ? n/a ? /b ? = ? n/ab ? 。 取整函數(shù)的若干性質(zhì) ? x1 ? x ? ? x ? ? x ? x+1； ? ? n/2 ? + ? n/2 ? = n。 ? 嚴(yán)格單調(diào)遞增： m n ? f(m) f(n)。 ? 則對(duì)所有的 n ? n3，有 ? f1(n) +g1(n) ? c1f(n) + c2g(n) ? c3f(n) + c3g(n)= c3(f(n) + g(n)) ? c32 max{f(n),g(n)} = 2c3h(n) = O(max{f(n),g(n)}) . 算法漸近復(fù)雜性分析中常用函數(shù) ? （ 1）單調(diào)函數(shù) ? 單調(diào)遞增： m ? n ? f(m) ? f(n) 。 ? 類似地，對(duì)于任意 g1(n) ? O(g(n)) ，存在正常數(shù) c2和自然數(shù) n2，使得對(duì)所有 n? n2，有 g1(n) ? c2g(n) 。 ? f(n)= ?(g(n)) ? a b. 漸近分析記號(hào)的若干性質(zhì) ? （ 1）傳遞性： ? f(n)= ?(g(n))， g(n)= ?(h(n)) ? f(n)= ?(h(n))； ? f(n)= O(g(n))， g(n)= O (h(n)) ? f(n)= O (h(n))； ? f(n)= ?(g(n))， g(n)= ? (h(n)) ? f(n)= ?(h(n))； ? f(n)= o(g(n))， g(n)= o(h(n)) ? f(n)= o(h(n))； ? f(n)= ?(g(n))， g(n)= ? (h(n)) ? f(n)= ? (h(n))； ? （ 2）反身性： ? f(n)= ?(f(n))； ? f(n)= O(f(n))； ? f(n)= ?(f(n)). ? （ 3）對(duì)稱性： ? f(n)= ?(g(n)) ? g(n)= ? (f(n)) . ? （ 4）互對(duì)稱性： ? f(n)= O(g(n)) ? g(n)= ? (f(n)) ； ? f(n)= o(g(n)) ? g(n)= ? (f(n)) ； ? （ 5）算術(shù)運(yùn)算： ? O(f(n))+O(g(n)) = O(max{f(n),g(n)}) ； ? O(f(n))+O(g(n)) = O(f(n)+g(n)) ； ? O(f(n))*O(g(n)) = O(f(n)*g(n)) ； ? O(cf(n)) = O(f(n)) ； ? g(n)= O(f(n)) ? O(f(n))+O(g(n)) = O(f(n)) 。 ? f(n)= ?(g(n)) ? a = b。 漸近分析中函數(shù)比較 ? f(n)= O(g(n)) ? a ? b。 ? 例如： 2n2 + 3n + 1 = 2n2 + ?(n) 表示 ? 2n2 +3n +1=2n2 + f(n)，其中 f(n) 是 ?(n)中某個(gè)函數(shù)。 ? f(n) ? ? (g(n)) ? g(n) ? o (f(n)) ? （ 5） 緊漸近界記號(hào) ? ? ? (g(n)) = { f(n) | 存在正常數(shù) c1,c2和 n0使得對(duì)所有 n? n0有： c1g(n) ? f(n) ? c2g(n) } ? 定理 1： ? (g
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1