你好!今天的課程與其他課程略有不同。它的不同之處在於它僅與 Java 間接相關。 也就是說,這個主題對每個程序員都非常重要。我們將討論算法。什麼是算法?簡而言之,它是為達到預期結果而必須完成的一些動作序列。我們在日常生活中經常使用算法。例如,每天早上您都有一項特定任務:去上學或上班,同時:
- 穿著衣服
- 乾淨的
- 美聯儲
- 使用鬧鐘叫醒。
- 衝個澡,把自己洗乾淨。
- 做早餐和一些咖啡或茶。
- 吃。
- 如果你前一天晚上沒有熨衣服,那就熨吧。
- 穿上衣服。
- 離開這房子。
- 購買或下載 1961 年版的韋氏第三版新國際詞典。
- 在這本詞典中找到我們列表中的每個名字。
- 在一張紙上,寫下名字所在的字典頁碼。
- 用紙片對名字進行排序。
for
您編寫一個執行此任務的 普通循環
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
這個算法的複雜度是多少?線性的,即O(n)。 程序必須執行的操作數量取決於傳遞給它的數字數量。如果數組中有 100 個數字,就會有 100 個動作(在屏幕上顯示字符串的語句)。如果數組中有 10,000 個數字,則必須執行 10,000 個操作。我們的算法可以以任何方式改進嗎?不行,無論如何,我們都得讓N遍遍歷數組,執行N條語句,才能在控制台上顯示字符串。考慮另一個例子。
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
我們有一個空的LinkedList
,我們在其中插入幾個數字。在我們的示例中,我們需要評估將單個數字插入到的算法複雜性LinkedList
,以及它如何取決於列表中元素的數量。答案是O(1),即復雜度不變。為什麼?請注意,我們在列表的開頭插入了每個數字。此外,您會記得,當您向 a 中插入一個數字時LinkedList
,元素不會移動到任何地方。鏈接(或引用)已更新(如果您忘記了 LinkedList 的工作原理,請查看我們的舊課程之一)。如果我們列表中的第一個數字是x
,並且我們在列表的前面插入數字 y ,那麼我們需要做的就是:
x.previous = y;
y.previous = null;
y.next = x;
當我們更新鏈接時,我們不關心 中已經有多少數字LinkedList
,無論是一還是十億。算法的複雜度是常數,即O(1)。