【算法與數(shù)據(jù)結(jié)構(gòu)】1 算法0基礎(chǔ)入門，詳解什么是算法？什么是線性查找法？

這篇具有很好參考價(jià)值的文章主要介紹了【算法與數(shù)據(jù)結(jié)構(gòu)】1 算法0基礎(chǔ)入門，詳解什么是算法？什么是線性查找法？。希望對大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

歡迎來到愛書不愛輸?shù)某绦蛟车牟┛? 本博客致力于知識分享，與更多的人進(jìn)行學(xué)習(xí)交流

本文收錄于算法與數(shù)據(jù)結(jié)構(gòu)體系專欄,本專欄是服務(wù)于0基礎(chǔ)者,一起完成從0到1的跨越

1.什么是算法?

就是一系列可以解決問題的 清晰的 可執(zhí)行的計(jì)算機(jī)指令
那么生活中有哪些算法?

問路:坐公交車到達(dá)某一站下車—>再轉(zhuǎn)某一個(gè)地鐵站這個(gè)地鐵站坐幾號線?從哪一站下車?下車以后從幾號地鐵口出去?—>再怎么走就能到了–>??

求解方程:一步一步的求解一元二次方程,這里涉及的每一步都是清晰可執(zhí)行的

這一系列的指令本質(zhì)其實(shí)就是一個(gè)算法: 解決了如何到達(dá)目的地的一個(gè)問題，解決了如何求得一個(gè)一元二次方程的解

1.1算法的五大特性

① 有限性:

一個(gè)算法不應(yīng)該是無限循環(huán)的,應(yīng)該在有限的時(shí)間里可以執(zhí)行完
有限時(shí)間 ≠ 時(shí)間短 : 假設(shè)一個(gè)算法需要萬年億年才能執(zhí)行完,那么從原則上講他也是一個(gè)算法,只不過他消耗的時(shí)間太長,這個(gè)算法并不實(shí)用而已,同樣的,不實(shí)用不代表沒有意義,研究算法恰恰是從這樣的一個(gè)看似不可行的算法出發(fā),一步一步的優(yōu)化它,最終得到一個(gè)可行的算法

② 確定性

它是一系列清晰的可執(zhí)行的計(jì)算機(jī)指令, 那么每一個(gè)指令本身是含義唯一的, 不會(huì)產(chǎn)生二義性
假設(shè)一個(gè)指令要求說出某校成績最高的學(xué)生,嚴(yán)謹(jǐn)來講,他就是會(huì)產(chǎn)生二義性的,"成績最高"在不同人眼里,可能理解到的含義不同 ,最終執(zhí)行的結(jié)果就不同(語文成績最高?數(shù)學(xué)成績最高?總成績最高)
含義唯一 ≠ 相同輸入會(huì)有相同輸出 : 對于一個(gè)隨機(jī)算法來說，那么很有可能輸入是同樣的一個(gè)數(shù)據(jù)，輸出的結(jié)果呢卻不相同

③可行性

算法中的每一步應(yīng)該是可行的
假設(shè)算法要求拿出最大的質(zhì)數(shù)，那么這個(gè)指令呢就是不可行的——質(zhì)數(shù)有無窮個(gè)的

④輸入

對于一個(gè)算法來說，它是有輸入的
一個(gè)函數(shù)我們就可以把它理解成一個(gè)算法它內(nèi)部執(zhí)行了一系列的運(yùn)算獲得了一些結(jié)果那么對于一個(gè)函數(shù)來說我們是可以給它指定輸入的參數(shù) 并且指定返回的類型
函數(shù)沒有任何的輸入的參數(shù) ≠ 算法沒有輸入 : 算法的輸入的概念是更加廣義的，對于一個(gè)函數(shù)來講，可能并沒有輸入的參數(shù)，但對于一個(gè)算法來說，他肯定是有他需要操作的對象的，那么他所操作的這些對象就是這個(gè)算法的輸入

具體表現(xiàn)在程序中，一個(gè)算法操作的對象有可能定義在一個(gè)類中，它是一個(gè)成員變量，是一個(gè)全局變量，它不是這個(gè)函數(shù)的參數(shù)，那么它也是這個(gè)算法的輸入，甚至有可能一個(gè)算法操作的對象本身隱藏在這個(gè)算法的語義中——比如設(shè)計(jì)一個(gè)算法，這個(gè)算法他做的事情就是生成零這個(gè)數(shù)字，所以這個(gè)算法內(nèi)部的邏輯直接通過return 0返回零就好了，那么這個(gè)算法看起來沒有輸入的值，但是其實(shí)我們必須在數(shù)學(xué)上定義清楚了0：0到底是什么？才能返為零這樣的一個(gè)數(shù)字。那么從數(shù)學(xué)上擁有了零這個(gè)概念本身就是我們這個(gè)算法的輸入

一個(gè)算法是有輸入的，這個(gè)輸入本身應(yīng)該站在一個(gè)更高的層次去理解，它可以是一個(gè)很抽象的輸入

⑤輸出

對于一個(gè)算法來說，它是有輸出的
與輸入同理，一個(gè)函數(shù)可能沒有返回值，返回值是void類型，這不意味著這個(gè)算法沒有輸出

比如一個(gè)算法做的事情是在屏幕中繪制了一個(gè)圓，那么這樣的一個(gè)繪制函數(shù)很有可能它的返回類型是void，但是這個(gè)算法本身確實(shí)在我們的這個(gè)屏幕中把這個(gè)圓繪制出來了，這個(gè)繪制的結(jié)果就是這個(gè)算法的輸出。

或者一個(gè)算法做的事情就是休眠x分鐘，x是一個(gè)輸入，那么對于這個(gè)算法來說，沒有返回值，只是執(zhí)行了休眠x分鐘這樣的一個(gè)操作，返回值是void，但是這個(gè)算法的輸出就是我們的這個(gè)程序真的休眠了x分鐘，在這x分鐘中不進(jìn)行任何的響應(yīng)

2.線性查找法

2.1生活中的線性查找法

【算法與數(shù)據(jù)結(jié)構(gòu)】1 算法0基礎(chǔ)入門，詳解什么是算法？什么是線性查找法？

高三的時(shí)候，老班經(jīng)常晚自習(xí)進(jìn)行模擬考試，在批完卷子后，由課代表將試卷發(fā)下去，此時(shí)每張卷子都有對應(yīng)的同學(xué)名字，這時(shí)有的同學(xué)就會(huì)主動(dòng)去課代表那里找到自己的卷子，而方法就是：把這一張?jiān)嚲砟玫阶约旱拿媲?看一下第一張卷子是不是自己的，如果不是，那么看第二張卷子是不是自己的，如果還不是，看第三張卷子是不是自己的，以此類推…比如說，看到第五張卷子，發(fā)現(xiàn)這張卷子就是自己的，那么就找到了，這就叫做線性查找法： 一個(gè)一個(gè)的去尋找自己想要找到的那個(gè)目標(biāo)元素
上面的一張卷子，可以理解成就是在一個(gè)數(shù)組中查找某一個(gè)元素，數(shù)組是非常簡單的這樣一種數(shù)據(jù)結(jié)構(gòu)

2.2 計(jì)算機(jī)中的線性查找法

假設(shè)我們就是在一個(gè)叫做data這樣的數(shù)組中查找元素16，數(shù)組中一共有八個(gè)元素，八個(gè)元素所對應(yīng)的索引是0 1 2 3 4 5 6 7，對應(yīng)的值分別是24 18 12 9 16 66 32 4
想在這個(gè)數(shù)組中查找目標(biāo)16，應(yīng)用線性查找法的思路，應(yīng)該怎樣找？
- 設(shè)置一個(gè) 索引i，初始的時(shí)候是0
- 從0開始查看這個(gè)data數(shù)組中對應(yīng)的元素是不是我們的目標(biāo)
- data[0]的值是24≠16，進(jìn)行i++(其實(shí)這就是一個(gè)循環(huán)的過程)
- data[1]的值是18≠16，繼續(xù)進(jìn)行i++
- …
- data[4]的值是16=16，我們就找到了這個(gè)結(jié)果
上述過程就叫做線性查找法——對于這個(gè)線性查找法，整個(gè)算法的輸入是什么？
- 這個(gè)輸入包含有一個(gè)數(shù)組——即我們要從一堆試卷中找到屬于自己的那一張?jiān)嚲恚紫纫羞@一堆試卷，在算法中用一個(gè)數(shù)組來表示
- 輸入還應(yīng)該包含一個(gè)目標(biāo)元素 ——知道自己的名字是什么，才能在這一點(diǎn)試卷中找到屬于自己的那一張?jiān)嚲?，在上面這個(gè)例子中，目標(biāo)元素其實(shí)就是16
對于這個(gè)線性查找法，整個(gè)算法的輸出是什么？
- 設(shè)計(jì)這個(gè)算法的輸出是目標(biāo)元素所在的索引——例子中16這個(gè)元素索引為4，這個(gè)算法返回就應(yīng)該是4
- 也有可能你想要查找的這個(gè)目標(biāo)在數(shù)組中不存在——返回-1，因?yàn)?1不是一個(gè)合法的索引值 (對于任何一個(gè)索引值來說肯定是大于等于零的一個(gè)值)

3.線性查找法的實(shí)現(xiàn)

3.1初步實(shí)現(xiàn)

public class LinearSearch {
    /*
    @function 線性查找的方法
    @param data 整型數(shù)組 待查找的數(shù)組
    @param terget 整型數(shù)組 查找的目標(biāo)
    @return 整型 找到的索引值或-1
     */
    public int search(int[] data, int target) {
        for (int i = 0; i < data.length; i++) {  
            if (data[i] == target)
                return i;    //如果找到目標(biāo)，返回對應(yīng)的索引值
        }
        return -1;          //如果沒有找到目標(biāo)，返回-1
    }

    public static void main(String[] args) {

        //準(zhǔn)備用于查找的數(shù)組
        int[] data = {24, 18, 12, 9, 16, 66, 32, 4};

         LinearSearch ls = new LinearSearch(); //聲明一個(gè)LinearSearch的對象
         
        //調(diào)用LinearSearch的search(),查找目標(biāo)16
        //將返回的結(jié)果賦值給一個(gè)整型變量res
        int res = ls.search(data, 16); 
        System.out.println(res); //輸出res

        int res2 = ls.search(data,666); //查找目標(biāo)666
        System.out.println(res2);

    }
}

運(yùn)行結(jié)果

3.2 代碼優(yōu)化

3.2.1優(yōu)化1

沒有必要聲明一個(gè)LinearSearch的對象，可以將search()改成靜態(tài)的方法，這樣在調(diào)用search()的時(shí)候，就可以直接用LinearSearch這個(gè)類名進(jìn)行調(diào)用search()

用戶不需要?jiǎng)?chuàng)建一個(gè)LinearSearch的對象，他只希望使用線性查找的方式從某個(gè)數(shù)組中查找一個(gè)元素，我們將這個(gè)方法寫成static，直接讓用戶調(diào)用這個(gè)方法就好了，而不需要new 一個(gè)新對象

public class LinearSearch {
    /*
    @function 線性查找的方法，static將其設(shè)置為靜態(tài)方法
    @param data 整型數(shù)組 待查找的數(shù)組
    @param terget 整型數(shù)組 查找的目標(biāo)
    @return 整型 找到的索引值或-1
     */
    public static int search(int[] data, int target) {
        for (int i = 0; i < data.length; i++) {  
            if (data[i] == target)
                return i;    //如果找到目標(biāo)，返回對應(yīng)的索引值
        }
        return -1;          //如果沒有找到目標(biāo)，返回-1
    }

    public static void main(String[] args) {

        //準(zhǔn)備用于查找的數(shù)組
        int[] data = {24, 18, 12, 9, 16, 66, 32, 4};
        
        //調(diào)用LinearSearch的search(),查找目標(biāo)16
        //將返回的結(jié)果賦值給一個(gè)整型變量res
        int res = LinearSearch.search(data, 16); 
        System.out.println(res); //輸出res

        int res2 = LinearSearch.search(data,666); //查找目標(biāo)666
        System.out.println(res2);

    }
}

3.2.2 優(yōu)化2

上述優(yōu)化后，雖然用戶能直接通過LinearSearch.search()調(diào)用方法，但是用戶依然可以進(jìn)行“new一個(gè)LinearSearch類的對象”的操作，如何阻止這一操作？可以在LinearSearch中將LinearSearch的構(gòu)造函數(shù)聲明為私有的即可

public class LinearSearch {
	//將LinearSearch的構(gòu)造函數(shù)聲明為私有
	private LinearSearch(){}
    /*
    @function 線性查找的方法，static將其設(shè)置為靜態(tài)方法
    @param data 整型數(shù)組 待查找的數(shù)組
    @param terget 整型數(shù)組 查找的目標(biāo)
    @return 整型 找到的索引值或-1
     */
    public static int search(int[] data, int target) {
        for (int i = 0; i < data.length; i++) {  
            if (data[i] == target)
                return i;    //如果找到目標(biāo)，返回對應(yīng)的索引值
        }
        return -1;          //如果沒有找到目標(biāo)，返回-1
    }

    public static void main(String[] args) {

        //準(zhǔn)備用于查找的數(shù)組
        int[] data = {24, 18, 12, 9, 16, 66, 32, 4};
        
        //調(diào)用LinearSearch的search(),查找目標(biāo)16
        //將返回的結(jié)果賦值給一個(gè)整型變量res
        int res = LinearSearch.search(data, 16); 
        System.out.println(res); //輸出res

        int res2 = LinearSearch.search(data,666); //查找目標(biāo)666
        System.out.println(res2);

    }
}

雖然將LinearSearch的構(gòu)造函數(shù)聲明為私有，但是上述代碼中的main()里依舊可以進(jìn)行“new一個(gè)LinearSearch類的對象”的操作

這是因?yàn)楫?dāng)前的main()是LinearSearch類的內(nèi)部的函數(shù)，所以它依然可以訪問到LinearSearch中的所有方法（包括私有方法），但這個(gè)優(yōu)化的思想是沒有問題的，是需要我們學(xué)習(xí)的

??今天的內(nèi)容就到這里啦?? ??希望對大家的學(xué)習(xí)有所幫助?? ??歡迎大家來訪，我們共同學(xué)習(xí)交流??

【算法與數(shù)據(jù)結(jié)構(gòu)】1 算法0基礎(chǔ)入門，詳解什么是算法？什么是線性查找法？文章來源地址http://www.zghlxwxcb.cn/news/detail-407706.html

到了這里，關(guān)于【算法與數(shù)據(jù)結(jié)構(gòu)】1 算法0基礎(chǔ)入門，詳解什么是算法？什么是線性查找法？的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！