演算法規模

㈠ 評價演算法復雜度時，問題的規模的定義是什麼

問題規模本身並沒有非常精準的定義，一般是指運行時間t和輸入參數個數n的關系用O(n)表示，比如max([x])就是O(n)而冒泡排序則是O(n^2)。

演算法復雜度，即演算法在編寫成可執行程序後，運行時所需要的資源，資源包括時間資源和內存資源。
同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。
（1）時間頻度
一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。演算法的時間復雜度是指執行演算法所需要的計算工作量。
（2）時間復雜度
在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間復雜度概念。
一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。
在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n^2+3n+4與T(n)=4n^2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n^2)。

㈡ 演算法的時間復雜度僅與問題的規模有關

不一定直與問題規模有關，而是與該問題取值空間規模有關。

㈢ 遺傳演算法是不是種群規模選取越大，全局最優解越好！

種群規模是指任意一代中的個體總數，這個是人為設定的，種群規模越大越可能找內到全容局解，但運行時間也相對較長，一般在40-100之間取值，像我就習慣選60.
至於你所處理的問題，可以對比不同的種群規模下最優解和運行時間，然後折衷取。

㈣ 遺傳演算法種群規模是怎麼得到的

種群規模是指任意一代中的個體總數，這個是人為設定的，種群規模越大越可能回找到全局解，但運行時答間也相對較長，一般在40-100之間取值，像我就習慣選60.
至於你所處理的問題，可以對比不同的種群規模下最優解和運行時間，然後折衷取。

㈤ 演算法的時間復雜度僅與問題的規模相關嗎

1.while循環執行次數是log(3,n),因此時間復雜度是O(log(n))
2.while循環執行次數是版n-1,因此時權間復雜度是O(n)
3.while循環執行次數是n,因此時間復雜度是O(n)
4.while循環執行次數與n無關,因此時間復雜度是O(1)

㈥ 5 估算演算法時間復雜度時考慮的問題規模通常是指演算法求解問題的( )。

估算演算法時間復雜度時考慮的問題規模通常是指演算法求解問題的輸入量。

㈦ 對於大規模TSP問題，為什麼遍歷演算法不可行而貪心演算法可行

TSP屬於NPC問題，來一般只能靠近似自演算法求出近似解，問題規模小的時候，可以直接窮舉問題空間，得出最優解，不過問題規模一大就不行了，問題空間是指數暴漲的，這時候只能退而求其次，求近似最優解，而對應的近似演算法中會大量使用貪心策略，所以其實不是可不可行的問題，貪心犧牲了 解的精度（求得的不一定是最優解），但換來了時間上可觀的節約（直接降到多項式）。

㈧ 演算法的時間復雜度

在一般情況下復，一個算製法的時間復雜度是（關於問題規模n）的函數。 設待處理問題的規模為n，若一個演算法的時間復雜度為一個常數，則表示成數量級的形式為（O（1）），若為n*log25n，則表示成數量級的形式為（O（nlogn） ）。

㈨ 如果某演算法對於規模為n的問題的時間耗費為T(n)=3n3，在一台計算機上運行時間為t秒，則在另

從數學上定義，給定演算法A，如果存在函數F(n)，當n=k時，F(k)表示演算法A在輸入規模為版k的情況下的運行時間，則稱權F(n)為演算法A的時間復雜度。這里首先要明確輸入規模的概念。關於輸入規模，不是很好下定義，非嚴格的講，輸入規模是指演算法A所接受輸入的自然獨立體的大小。例如，對於排序演算法來說，輸入規模一般就是待排序元素的個數，而對於求兩個同型方陣乘積的演算法，輸入規模可以看作是單個方陣的維數。為了簡單起見，總是假設演算法的輸入規模是用大於零的整數表示的，即n=1,2,3,……,k,…… 對於同一個演算法，每次執行的時間不僅取決於輸入規模，還取決於輸入的特性和具體的硬體環境在某次執行時的狀態。所以想要得到一個統一精確的F(n)是不可能的。為了解決這個問題，做以下兩個說明： 1.忽略硬體及環境因素，假設每次執行時硬體條件和環境條件是完全一致的。 2.對於輸入特性的差異，將從數學上進行精確分析並帶入函數解析式。

㈩ 演算法里的輸入規模是什麼

輸入規模決定演算法

運算量 n！ 2^n n^3 n^2 nlogn n
最大規模 11 26 464 10000 4.5*10^6 1000000000
速度擴大兩倍 11 27 587 14142 8.6*10^6 2000000000
這個表給出了機器速度擴大兩倍後，演算法所能解決的規模的對比。可以看出，n！和2n不僅能解決的問題規模十分小,而且增長緩慢；最快的nlogn和n演算法不僅解決問題
的規模大，而且增長快。我們把漸進時間復雜為多項式的演算法稱為多項式時間演算法(polymonial-time algorithm)，也稱有效演算法；而n!或者2^n這樣低效演算法稱為指數時間演算法（exponential-time algorithm）.
盡管如此，考慮到目前主流機器的執行速度，多數演算法競賽所選取的數據規模基本符合此表。例如，一些指明n<=8的題目，可能n！的演算法已經足夠，n<=20的題目需要2^n的演算法,而n<=300的題目可能就需要用至少n^3的多項式演算法.