關於演算法時間複雜度分析的問題

誰告訴你分析的時間複雜度是用比較的數量來衡量的？

執行演算法所需的時間無法從理論上計算，只有在計算機上執行測試時才能知道。 但是不可能也沒有必要在機器上測試每個演算法，我們只需要知道哪種演算法花費更多時間，哪種演算法花費更少的時間。 演算法花費的時間與演算法中語句的執行次數成正比。

在演算法中執行語句的次數稱為語句頻率或時間頻率。 表示為 t（n）。

一般來說，演算法的基本運算重複的次數是模組n的函式f（n），因此演算法的時間複雜度記錄為：t（n）=o（f（n））。

分析：隨著模組n的增加，演算法執行時間的增長率與f（n）的增長率成正比，因此f（n）越小，演算法的時間複雜度越低，演算法的效率越高。

在計算時間複雜度時，首先找出演算法的基本操作，然後根據相應的語句確定其執行次數，然後找到與t（n）相同的數量級（其同數量級如下：1，log2n，n，nlog2n，n平方，n次方，n次方，2n次方， n!）， f（n） = 這個數量級，如果 t（n） f（n） 找到獲得常數 c 的極限，則時間複雜度 t（n） = o（f（n））。

通常，時間複雜度是根據演算法中最複雜的迴圈（例如乙個）來衡量的。

for(i = 0;i < n;i ++

for(j = 0;j < n;j ++

他有多少個孤獨的人並不重要。

for(i = 0;i < n;i ++

他的時間複雜度是 o（n2）。

它不會是 o（n2） +o（n） +o（n） +o（2n）...這樣。

對於複雜度為 o（n 3） 的方程 3n 3+n 2+8n，我們只考慮最大項數對方程值的影響，其他語句如變數賦值以 n 的係數計算。

這種時間複雜度分析非常粗糙，實時複雜度分析是用圖靈機來描述的。

演算法的時間複雜度是定性描述演算法執行時間的函式。

這是乙個函式，表示演算法輸入值的字串的長度。 時間複雜度通常用大 o 符號表示，不包括該函式的低階項和第一係數。 這樣，時間複雜度可以稱為漸近，即當輸入值的大小接近無窮大時。

演算法的時間複雜度取決於什麼演算法的時間複雜度取決於要處理的資料的狀態和問題的大小。 演算法中的指令描述了一種計算，該計算在執行時可以從初始狀態和（可能是空的）初始輸入開始，經過有限且定義明確的一系列狀態，最後產生輸出並在最終狀態停止。 從一種狀態到另一種狀態的轉變不一定是確定的。

某些演算法（包括隨機化演算法）包含一些隨機輸入。

這裡我們只列舉一些簡單的演算法時間複雜度分析。

週期的時間複雜度為 0 （n）。

雙週期的時間複雜度為 0 （n2

三重週期的時間複雜度為 0 （n3

等等。 讓我們以乙個簡單的洩漏列表為例。

如果你看一下這個，你可能會估計出日誌有多大。 根據評估機的計算速度判斷是否超時。

int 的範圍為 -2147483648 2147483647。 大概在 2 109

多頭的範圍大概是1018

一些數字應該注意功率。

o(n!)、o(2n)、o(n

2)、o(nlogn)、o(n)、o(logn)、o(1)..

代表：最壞的情況。

正整數的階乘是所有小於或等於該數字的正整數的乘積，階乘 0 為 1。 自然數 n 的階乘寫為 n！。 1808 年，Keystone Carman 引入了這種符號。

n 的 n 次方，是上標的意思。

如果 a = n（a>0 和 a ≠ 1），則數字 x 稱為底數 n 的對數，表示為 x=logan，讀作底數 n 的對數，其中 a 稱為對數的底數，n 稱為真數。

其中 x 是自變數，函式的域是 （0， + 是 x>0。 它實際上是指數函式的倒函式，可以表示為 x= a。 因此，指數函式中 a 的定義也適用於對數函式。

在描述演算法的複雜度時，通常使用o（1）、o（n）、o（logn）和o（nlogn）來表示相應演算法的時間複雜度，即演算法時空複雜度的表示。 它不僅用於表示時間複雜性，還用於表示空間複雜性。

o 括號中有乙個函式，用於指示演算法消耗的時間和空間與資料增長量之間的關係。 其中 n 表示輸入資料量。

時間複雜度為o（n），表示資料量增加數倍，耗時量也增加數倍，呈線性增加，如常見的：

時間複雜度 o（n 2） 表示當資料量增加 n 倍時，所花費的時間增加 n 的平方倍，這比線性的時間複雜度更高。 例如：

O（nlogn）也是一樣，即n乘以logn，當資料增加256倍時，所花費的時間增加256*8=2048倍。 這種複雜度高於線性且低於平方。 例如：

當資料增加 n 倍時，所用時間增加 logn 次（這裡的對數以 2 為基礎，例如，當資料增加 256 倍時，所花費的時間僅增加 8 倍，低於線性時間複雜度）。 例如：

o（1）是時空複雜度最低的，即時間和空間消耗與輸入資料的大小無關，無論輸入資料增加多少倍，時間和空間消耗都保持不變。 例如：

代入 n 之後的值，以及時間與時間的關係10 8 = > 秒，最大的 n 是：

o（1）當一般時間複雜度達到2 n（指數）以上時，我們基本上不使用這樣的演算法，太不切實際了。 例如，河內塔問題演算法的遞迴實現為 o（2 n）。

平方階 （n 2） 演算法幾乎無法使用，而 nlogn 和較小的時間複雜度演算法是非常有效的演算法。

空間複雜性。

氣泡排序、簡單選擇排序、堆排序、直接插入排序，Hill 排序的空間複雜度為 o（1），因為需要乙個臨時變數來交換元素的位置，（另外，在遍歷序列時，少用乙個變數來做索引）。

快速排序空間複雜度是 logn（因為遞迴呼叫），合併排序空間複雜度是 o（n），需要乙個大小為 n 的臨時陣列。

基數排序的空間複雜度為o（n），桶排序的空間複雜度不確定。 源語言。

**的執行頻率為迴圈語句在迴圈中的執行次數，等於12+3+...n-1=n(n-1)/2

時間複雜度為 o（n 2）。

一般情況下，我認為如果演算法時間比較複雜，在這種情況下，可以直接從後台跟著三個問題走，這個選擇就好了。

您可以將其上傳到專業軟體檢視演算法。