關於算法分析的一些問題

Question

呃，嗨！那麼，我正在談論與算法相關的「O（n）」和「o（n）」。我不知道技術名稱，然後我稱之爲「算法分析」（對不起）。無論如何，問題：

1. 嗯，嗯......我怎麼能「分析」的算法，以確定他們是「爲O（n/2）」，例如？什麼考慮？
2. 例如，在排序算法中，「n」是要排序的元素的數量，括號內的操作是排序它們的時間。但我確實在一個線程上看到，在get算法上是O（n/4），但我不能將「n」表示爲要獲取的對象的數量，或者真的是這樣嗎？或者根據算法的類型而變化？
3. 一些關於此的重要信息，我需要知道嗎？

我對我的英語很抱歉，如果我確實使用了非常「膚淺」的詞彙。

Answer 1

O爲算法的複雜性。可能有幾種類型的複雜性。您可以測量時間複雜性，即算法的時間複雜程度。或者在記憶中。或者在磁盤存儲空間。後兩者非常相似。

時間複雜度：根據輸入大小確定所需的操作數。

內存或磁盤存儲的複雜性：確定多少空間將根據輸入的大小進行分配。

爲O（n/2）的時間複雜性意味着你將需要處理一半的操作比實際輸入的大小。

由於輸入是一個正整數，要能夠做到分析的東西，你需要假設N - >無窮大，即是，你必須輸入的項目很多。

然後爲O（n/2）是線性複雜性，因爲第（n/2）」 = 0.5。 0.5是一個標量值，標量並沒有真正改變無窮大的複雜性。當您的輸入數據有限時，實際上存在差異，但這是另一個需要解決的問題。所以

爲O（n/2）= <>爲O（n）

由於兩個是線性的，即使Y的線= N/2是從Y的線= n個不同的。

爲O（n^2）更復雜，因爲（N^2）」 = 2 * N。

因此，要理解的複雜性，你需要了解它描述了複雜的函數的導數（或差異在多個維度的情況下）。如果描述所有可能輸入的操作次數，則可以正確找到該功能。

確定複雜的例子：

讓我們考慮的情況下，當我們有一個有限，有序集數，我們正在尋找一個具體的數字。我們猜測第一次中間。如果我們猜對了，算法會停止。如果不是，那麼我們在上半年以類似的方式檢查數字，如果這個數字實際上小於我們在給定指數找到的那個數字，那麼在下半個數字中。這種算法被稱爲二分搜索。那麼，我們如何確定其複雜性呢？首先，我們需要觀察一下，我們有可能從第一次就猜測這個位置，所以最好的情況是O（1）。但是，如果我們不那麼幸運，我們可能需要多次減半。所以複雜性問題被簡化爲：我們可能需要多少次才能將這個集合減半？這是數字，因爲2的冪將產生輸入的大小。這是對數的定義，所以二分查找是對數的。

當你計算存儲複雜度時，你做了類似的計算。

Answer 2

你基本上要求一個關於如何分析算法運行時間的答案。這沒有捷徑，你必須研究這個理論。你可以谷歌它。下面是從那裏你可以開始一些鏈接：

How to find time complexity of an algorithm

introduction to algorithm complexty