在時(shí)間復(fù)雜度上比較分支限界法和回溯法？別說廢話，分支邊界和回溯是兩種不同的搜索方法，它們屬于并行搜索，不是誰包含誰。1）回溯方法一般采用深度優(yōu)先搜索解空間，并用邊界函數(shù)進(jìn)行修剪2）分支邊界一般采用廣度

在時(shí)間復(fù)雜度上比較分支限界法和回溯法？

別說廢話，分支邊界和回溯是兩種不同的搜索方法，它們屬于并行搜索，不是誰包含誰。

1）回溯方法一般采用深度優(yōu)先搜索解空間，并用邊界函數(shù)進(jìn)行修剪

2）分支邊界一般采用廣度優(yōu)先搜索解空間，在回溯法中采用優(yōu)先級(jí)隊(duì)列進(jìn)行剪枝，解空間中的節(jié)點(diǎn)可以多次出現(xiàn)，但分支邊界只出現(xiàn)一次，不存在回溯。怎么能說分支邊界是回溯的

因?yàn)榕ｎD迭代法的理論復(fù)雜度不能代表實(shí)際的時(shí)間復(fù)雜度。據(jù)我的導(dǎo)師介紹，牛頓迭代法的算法復(fù)雜度是在二三十年前由IBM的研究人員帶領(lǐng)的一群人研究的，最后復(fù)雜度降到了n^（2個(gè)小數(shù)字）。然而，這種復(fù)雜性不足以解釋為什么它在實(shí)踐中會(huì)迅速收斂。類似的問題包括“梯度下降法的收斂速度為何快或慢”、“內(nèi)點(diǎn)法為何沒有算法復(fù)雜性分析”等。