線性查找，肯定是以線性的方式，在集合或數(shù)組中查找某個(gè)元素。

通過(guò)代碼來(lái)理解線性查找

什么叫"線性"?還是在代碼中體會(huì)吧。

首先需要一個(gè)集合或數(shù)組，如何得到呢？就生成一個(gè)固定長(zhǎng)度的隨機(jī)數(shù)組吧。然后輸入一個(gè)查找key，如果找到就返回元素的索引，沒(méi)找到就返回-1，就這么簡(jiǎn)單。

    class Program
    {
        private static int[] arr;
        private static Random r = new Random();
        static void Main(string[] args)
        {
            SeedData(10);
            ShowArray();
            Console.WriteLine("\n");
            Console.WriteLine("請(qǐng)輸入要查找的整型數(shù)");
            var temp = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("您要查找的{0}所在的位置是{1}", temp, LinearSearch(temp));
            Console.ReadKey();
        }
        //線性查找
        private static int LinearSearch(int key)
        {
            for (int i = 0; i < arr.Length; i++)
            {
                if (arr[i] == key) return i; //找到就返回索引
            }
            return -1;//如果沒(méi)找到就返回-1
        }
        //數(shù)組的種子數(shù)據(jù)
        private static void SeedData(int size)
        {
            arr = new int[size];
            for (int i = 0; i < size; i++)
            {
                arr[i] = r.Next(1, 100);
            }
        }
        //打印數(shù)組的所有元素
        private static void ShowArray()
        {
            foreach (var item in arr)
            {
                Console.Write(item + " ");
            }
        }
    }

以上，我們自己可以定義什么叫"線性查找"了。就是說(shuō)，當(dāng)我們輸入一個(gè)查找的key，是按順序依次查找集合中的每個(gè)元素(實(shí)際是通過(guò)循環(huán)遍歷)，如果找不到就返回一個(gè)值，比如-1，如果找到就返回該元素的索引位置。

時(shí)間復(fù)雜度

線性查找只是查找的一種最簡(jiǎn)單的算法，還有其它相對(duì)復(fù)雜的算法。如何來(lái)衡量各種算法的效率呢，答案是用"時(shí)間復(fù)雜度"來(lái)衡量的。任何的概念來(lái)源于實(shí)踐，并不是憑空產(chǎn)生的，"時(shí)間復(fù)雜度"也一樣。

O(1)

假設(shè)一個(gè)數(shù)組中有10個(gè)元素，需要比較第一個(gè)元素是否等于第二個(gè)元素，算法只需要運(yùn)行一次就可以得出結(jié)果。如果數(shù)組中有100個(gè)元素呢？算法還是運(yùn)行一次就得到結(jié)果。于是，人們就想：算法的運(yùn)行和數(shù)組大小沒(méi)有關(guān)系，就把這種算法叫做"常量運(yùn)行時(shí)間"吧。但還不夠直觀，用什么圖形表示呢？人們想出就用O(1)來(lái)表示吧。

O(1)雖然很直觀，但很容易產(chǎn)生歧義。有些人認(rèn)為：只有算法運(yùn)行一次，并且運(yùn)行的次數(shù)不隨數(shù)組大小改變，就可以用O(1)表示了。這是很明顯的"望文生義"。O(1)更準(zhǔn)確的解釋是：算法的運(yùn)行次數(shù)是一個(gè)常量，不會(huì)隨著數(shù)組大小而改變。

O(n)

生活的精彩來(lái)自多樣性。假設(shè)一個(gè)數(shù)組中還是10個(gè)元素，需要比較第一個(gè)元素是否等于數(shù)組中任何其它元素，算法需要運(yùn)行9次。如果數(shù)組中有100個(gè)元素呢，算法需要運(yùn)行99次，也就是n-1次，算法運(yùn)行的次數(shù)隨著n的不同而發(fā)生改變。人們把這種算法寫(xiě)成O(n)，1可以忽略不計(jì)，讀成"n階"。

O(n²)

假設(shè)還有一種算法，需要比較數(shù)組中的任何元素于其它元素是否相等。第一個(gè)元素，需要和后面n-1個(gè)元素比較，第二個(gè)元素需要和除了第一個(gè)元素之外的其后面n-2個(gè)元素比較......也就是：(n-1) + (n-2) + ... + 2 + 1,這個(gè)公式用筆在紙上簡(jiǎn)單推算一下，還可以提煉為n²/2-n/2，隨著n的增大，常量因子可以忽略，寫(xiě)成O(n²),稱(chēng)為"平方運(yùn)行時(shí)間",讀成"n²階"。

當(dāng)n是幾萬(wàn)，O(n²)算法在今天每秒運(yùn)行幾十億次的個(gè)人計(jì)算機(jī)上，不會(huì)有明顯的性能影響。但如果n變成幾百萬(wàn)，就要求幾萬(wàn)億次計(jì)算，這樣可能要幾個(gè)小時(shí)來(lái)執(zhí)行。更有甚者，如果n變成幾十億，計(jì)算需要幾十年來(lái)完成。所以，每種算法都有它的適用范圍。

現(xiàn)在，可以稍微完整地定義"時(shí)間復(fù)雜度"了，它是一個(gè)函數(shù)，定量描述了算法的運(yùn)行時(shí)間。時(shí)間復(fù)雜度是在最壞情況下的時(shí)間復(fù)雜度。

常見(jiàn)的時(shí)間復(fù)雜度有：

• O(1), 常數(shù)階，比如Hash表的查找
• O(log2n)，對(duì)數(shù)階，比如二分查找
• O(n)，線性階
• O(nlog2n)，線性對(duì)數(shù)階，比如快速排序的平均復(fù)雜度
• O(n^2)，平方階，比如冒泡排序
• O(n^3)，立方階，比如求最短路徑的Floyd算法
• O(n^k)，k次方階
• O(2^n)，指數(shù)階，比如漢諾塔

什么是算法

是解決特定問(wèn)題求解步驟的描述。在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。

sum = 1     +     2     +     3 + ... + 100
sum = 100   +     99  +   98+ ... + 1
2*sum = 101*100 = 10100
sum = 5050

以上就是針對(duì)1到100求和的算法。對(duì)，是在18世紀(jì)，一個(gè)德國(guó)的小村莊，一個(gè)叫高斯的小孩想出來(lái)的，就這么神奇！

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接

最新評(píng)論