C++分治 小結(jié)

2023-09-20 09:23 更新
  • 分治算法是一種常見(jiàn)的算法設(shè)計(jì)策略，包括分（劃分）和治（合并）兩個(gè)階段，通?；谶f歸實(shí)現(xiàn)。
  • 判斷是否是分治算法問(wèn)題的依據(jù)包括：?jiǎn)栴}能否被分解、子問(wèn)題是否獨(dú)立、子問(wèn)題是否可以被合并。
  • 歸并排序是分治策略的典型應(yīng)用，其遞歸地將數(shù)組劃分為等長(zhǎng)的兩個(gè)子數(shù)組，直到只剩一個(gè)元素時(shí)開(kāi)始逐層合并，從而完成排序。
  • 引入分治策略往往可以帶來(lái)算法效率的提升。一方面，分治策略減少了操作數(shù)量；另一方面，分治后有利于系統(tǒng)的并行優(yōu)化。
  • 分治既可以解決許多算法問(wèn)題，也廣泛應(yīng)用于數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)中，處處可見(jiàn)其身影。
  • 相較于暴力搜索，自適應(yīng)搜索效率更高。時(shí)間復(fù)雜度為 O(log?n) 的搜索算法通常都是基于分治策略實(shí)現(xiàn)的。
  • 二分查找是分治策略的另一個(gè)典型應(yīng)用，它不包含將子問(wèn)題的解進(jìn)行合并的步驟。我們可以通過(guò)遞歸分治實(shí)現(xiàn)二分查找。
  • 在構(gòu)建二叉樹(shù)問(wèn)題中，構(gòu)建樹(shù)（原問(wèn)題）可以被劃分為構(gòu)建左子樹(shù)和右子樹(shù)（子問(wèn)題），其可以通過(guò)劃分前序遍歷和中序遍歷的索引區(qū)間來(lái)實(shí)現(xiàn)。
  • 在漢諾塔問(wèn)題中，一個(gè)規(guī)模為 n 的問(wèn)題可以被劃分為兩個(gè)規(guī)模為 n?1 的子問(wèn)題和一個(gè)規(guī)模為 1 的子問(wèn)題。按順序解決這三個(gè)子問(wèn)題后，原問(wèn)題隨之得到解決。


以上內(nèi)容是否對(duì)您有幫助：
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號(hào)
微信公眾號(hào)

編程獅公眾號(hào)