算法復雜度的表示法

by Michael Olorunnisola

通過Michael Olorunnisola

用簡單的英語算法：時間復雜度和Big-O表示法 (Algorithms in plain English: time complexity and Big-O notation)

Every good developer has time on their mind. They want to give their users more of it, so they can do all those things they enjoy. They do this by minimizing time complexity.

每個優秀的開發人員都有自己的時間。 他們想給用戶更多的東西，以便他們可以做自己喜歡的所有事情。 他們通過最小化時間復雜度來做到這一點。

Before you can understand time complexity in programming, you have to understand where it’s most commonly applied: in the design of algorithms.

在您了解編程中的時間復雜性之前，您必須了解它最常應用的地方：在算法設計中。

那么，什么是算法？ (So what’s an algorithm, anyway?)

Simply put, an algorithm is a series of contained steps, which you follow in order to achieve some goal, or to produce some output. Let’s take for example your grandma’s recipe for baking a cake. Wait, does that count as an algorithm? Sure it does!

簡而言之，算法是一系列包含的步驟，為了實現某些目標或產生某些輸出，必須遵循這些步驟。 讓我們以您奶奶的烤蛋糕食譜為例。 等等，算作算法嗎？ 當然可以！

function BakeCake(flavor, icing){
"1. Heat Oven to 350 F2. Mix flour, baking powder, salt3. Beat butter and sugar until fluffy4. Add eggs.5. Mix in flour, baking powder, salt6. Add milk and " + flavor + "7. Mix further8. Put in pan9. Bake for 30 minutes
10." + if(icing === true) return 'add icing' + "
10. Stuff your face
"
}BakeCake('vanilla', true) => deliciousness

Algorithms are useful in our examination of time complexity because they come in all shapes and sizes.

由于算法具有各種形狀和大小，因此在我們檢查時間復雜度方面很有用。

In the same way you can slice a pie a 100 different ways, you can solve a single problem with many different algorithms. Some solutions are just more efficient, taking less time and requiring less space than others.

以相同的方式，您可以用100種不同的方式對一個餅進行切片，可以使用許多種不同的算法來解決一個問題。 與其他解決方案相比，某些解決方案效率更高，所需時間更少，占用的空間更少。

So the main question is: how do we go about analyzing which solutions are most efficient?

因此，主要問題是：我們如何分析哪些解決方案最有效？

Math to the rescue! Time complexity analysis in programming is just an extremely simplified mathematical way of analyzing how long an algorithm with a given number of inputs (n) will take to complete it’s task. It’s usually defined using Big-O notation.

求救數學！ 編程中的時間復雜度分析只是一種極其簡化的數學方法，用于分析具有給定數量輸入(n)的算法完成任務所需的時間。 通常使用Big-O表示法定義。

您問什么是大O符號？ (What’s Big O notation, you ask?)

If you promise you won’t give up and stop reading, I will tell you.

如果您保證不會放棄并停止閱讀，我會告訴您。

Big-O notation is a way of converting the overall steps of an algorithm into algebraic terms, then excluding lower order constants and coefficients that don’t have that big an impact on the overall complexity of the problem.

Big-O表示法是一種將算法的整體步驟轉換為代數項，然后排除對問題的整體復雜性影響不大的低階常量和系數的方法。

Mathematicians will probably cringe a bit at my “overall impact” assumption there, but for developers to save time, it’s easier to simplify things this way:

數學家可能會對我的“總體影響”假設有些畏縮，但是對于開發人員來說，為了節省時間，用這種方式簡化事情會更容易：

Regular       Big-O2             O(1)   --> It's just a constant number2n + 10       O(n)   --> n has the largest effect5n^2          O(n^2) --> n^2 has the largest effect

In short, all this example is saying is: we only look at the factor in our expression that has the potential greatest impact on the value that our expression will return. (This changes as the constant gets extremely large and n gets small, but let’s not worry about that for now).

簡而言之，此示例說明的是：我們僅查看表達式中對表達式返回的值具有最大潛在影響的因素。 (隨著常數變得非常大而n變得很小，這種情況會發生變化，但是現在我們不必擔心這一點)。

Below are some common time complexities with simple definitions. Feel free to check out Wikipedia, though, for more in-depth definitions.

以下是一些具有簡單定義的常見時間復雜性。 請隨意查看Wikipedia ，以獲得更深入的定義。

• O(1) — Constant Time: Given an input of size n, it only takes a single step for the algorithm to accomplish the task.
  O(1)-恒定時間：給定大小為n的輸入，算法只需一步即可完成任務。
• O(log n) — Logarithmic time: given an input of size n, the number of steps it takes to accomplish the task are decreased by some factor with each step.
  O(log n)-對數時間：給定大小為n的輸入，完成任務所需的步驟數會因每個步驟而減少一些。
• O(n) — Linear Time: Given an input of size n, the number of of steps required is directly related (1 to 1)
  O(n)—線性時間：給定大小為n的輸入，所需的步數直接相關(1到1)
• O(n2) — Quadratic Time: Given an input of size n, the number of steps it takes to accomplish a task is square of n.
  O(n2)—二次時間：給定大小為n的輸入，完成一項任務所需的步驟數為n的平方。
• O(C^n) — Exponential Time: Given an input of size n, the number of steps it takes to accomplish a task is a constant to the n power (pretty large number).
  O(C ^ n)—指數時間：在輸入大小為n的情況下，完成一項任務所需的步驟數是n次冪的常數(相當大的數字)。

With this knowledge in hand, lets see the number of steps that each of these time complexities entails:

掌握了這些知識之后，讓我們看一下這些時間復雜度所需要的步驟數：

let n = 16;O (1) = 1 step "(awesome!)"O (log n) = 4 steps  "(awesome!)" -- assumed base 2O (n) = 16 steps "(pretty good!)"O(n^2) = 256 steps "(uhh..we can work with this?)"O(2^n) = 65,536 steps "(...)"

As you can see, things can easily become orders of magnitude more complex depending on the complexity of your algorithm. Luckily, computers are powerful enough to still handle really large complexities relatively quickly.

如您所見，根據算法的復雜性，事情很容易變得復雜幾個數量級。 幸運的是，計算機功能強大，仍然可以相對快速地處理非常大的復雜性。

So how do we go about analyzing our code with Big-O notation?

那么，我們如何使用Big-O表示法分析代碼？

Well here are some quick and simple examples of how you can apply this knowledge to algorithms you might encounter in the wild or code up yourself.

好了，這里有一些快速簡單的示例，說明如何將這些知識應用于野外可能遇到的算法或自己編寫代碼。

We’ll use the data structures below for our examples:

我們將使用以下數據結構作為示例：

var friends = {'Mark' : true,'Amy' : true,'Carl' : false,'Ray' :  true,
'Laura' : false,
}
var sortedAges = [22, 24, 27, 29, 31]

O(1)-恒定時間 (O(1) — Constant Time)

Value look ups when you know the key (objects) or the index (arrays) always take one step, and are thus constant time.

當您知道鍵(對象)或索引(數組)總是邁出一步，并且時間恒定時，就會進行值查找。

//If I know the persons name, I only have to take one step to check:function isFriend(name){ //similar to knowing the index in an Array return friends[name]; 
};isFriend('Mark') // returns True and only took one stepfunction add(num1,num2){ // I have two numbers, takes one step to return the valuereturn num1 + num2
}

O(log n)-對數時間 (O(log n) — Logarithmic Time)

If you know which side of the array to look on for an item, you save time by cutting out the other half.

如果您知道要在陣列的哪一側查找某項，則可以省去另一半來節省時間。

//You decrease the amount of work you have to do with each stepfunction thisOld(num, array){var midPoint = Math.floor( array.length /2 );if( array[midPoint] === num) return true;if( array[midPoint] < num ) --> only look at second half of the arrayif( array[midpoint] > num ) --> only look at first half of the array//recursively repeat until you arrive at your solution}thisOld(29, sortedAges) // returns true //Notes//There are a bunch of other checks that should go into this example for it to be truly functional, but not necessary for this explanation.//This solution works because our Array is sorted//Recursive solutions are often logarithmic//We'll get into recursion in another post!

O(n)—線性時間 (O(n) — Linear Time)

You have to look at every item in the array or list to accomplish the task. Single for loops are almost always linear time. Also array methods like indexOf are also linear time. You’re just abstracted away from the looping process.

您必須查看數組或列表中的每個項目才能完成任務。 單次for循環幾乎總是線性時間。 像indexOf這樣的數組方法也是線性時間。 您只是從循環過程中抽象出來。

//The number of steps you take is directly correlated to the your input sizefunction addAges(array){var sum = 0;for (let i=0 ; i < array.length; i++){  //has to go through each valuesum += array[i]}return sum;
}addAges(sortedAges) //133

O(n2)—二次時間 (O(n2) — Quadratic Time)

Nested for loops are quadratic time, because you’re running a linear operation within another linear operation (or n*n = n2).

嵌套的for循環是二次時間，因為您正在另一個線性運算(或n * n =n2)內運行線性運算。

//The number of steps you take is your input size squaredfunction addedAges(array){var addedAge = [];for (let i=0 ; i < array.length; i++){ //has to go through each valuefor(let j=i+1 ; j < array.length ; j++){ //and go through them againaddedAge.push(array[i] + array[j]);}}return addedAge;
}addedAges(sortedAges); //[ 46, 49, 51, 53, 51, 53, 55, 56, 58, 60 ]//Notes//Nested for loops. If one for loop is linear time (n)//Then two nested for loops are (n * n) or (n^2) Quadratic!

O(2 ^ n)—指數時間 (O(2^n) — Exponential Time)

Exponential time is usually for situations where you don’t know that much, and you have to try every possible combination or permutation.

指數時間通常用于您不太了解的情況，并且您必須嘗試所有可能的組合或排列。

//The number of steps it takes to accomplish a task is a constant to the n power//Thought example//Trying to find every combination of letters for a password of length n

You should do time complexity analysis anytime you write code that has to run fast.

每當您編寫必須快速運行的代碼時，都應該進行時間復雜度分析。

When you have various routes to solve a problem, it is definitely wiser to create a solution that just works first. But in the long run, you’ll want a solution that runs as quickly and efficiently as possible.

當您有各種解決問題的途徑時，明智的做法是首先創建一個解決方案。 但是從長遠來看，您將需要一個盡可能快速高效地運行的解決方案。

To help you with the problem solving process, here are some simple questions to ask:

為了幫助您解決問題，以下是一些簡單的問題：

1. Does this solve the problem? Yes =>

1.這樣可以解決問題嗎？ 是 =>

1. Does this solve the problem? Yes =>

1.這樣可以解決問題嗎？ 是 =>

2. Do you have time to work on this

2.您有時間從事此工作嗎

2. Do you have time to work on this

2.您有時間從事此工作嗎

2. Do you have time to work on thisYes => go to step 3

2.您是否有時間進行此工作， 是 =>轉到步驟3

2. Do you have time to work on thisYes => go to step 3

2.您是否有時間進行此工作， 是 =>轉到步驟3

2. Do you have time to work on thisYes => go to step 3No => Come back to it later and go to step 6 for now.

2.您是否有時間進行此工作是 =>轉到步驟3 否 =>稍后再回到步驟6，現在轉到步驟6。

2. Do you have time to work on thisYes => go to step 3No => Come back to it later and go to step 6 for now.

2.您是否有時間進行此工作是 =>轉到步驟3 否 =>稍后再回到步驟6，現在轉到步驟6。

3. Does it cover all edge cases? Yes =>

3.它涵蓋所有邊緣情況嗎？ 是 =>

3. Does it cover all edge cases? Yes =>

3.它涵蓋所有邊緣情況嗎？ 是 =>

4. Are my complexities as low as possible ?

4.我的復雜程度是否盡可能低？

4. Are my complexities as low as possible ?

4.我的復雜程度是否盡可能低？

4. Are my complexities as low as possible ?No => rewrite or modify into a new solution –>go back to step 1

4.我的復雜程度是否盡可能低？ 否 =>重寫或修改為新解決方案–>返回步驟1

4. Are my complexities as low as possible ?No => rewrite or modify into a new solution –>go back to step 1

4.我的復雜程度是否盡可能低？ 否 =>重寫或修改為新解決方案–>返回步驟1

4. Are my complexities as low as possible ?No => rewrite or modify into a new solution –>go back to step 1Yes => go to step 5

4.我的復雜程度是否盡可能低？ 否 =>重寫或修改為新解決方案–>返回步驟1 是 =>轉到步驟5

4. Are my complexities as low as possible ?No => rewrite or modify into a new solution –>go back to step 1Yes => go to step 5

4.我的復雜程度是否盡可能低？ 否 =>重寫或修改為新解決方案–>返回步驟1 是 =>轉到步驟5

5. Is my code D.R.Y ? Yes =>

5.我的代碼是DRY嗎？ 是 =>

5. Is my code D.R.Y ? Yes =>

5.我的代碼是DRY嗎？ 是 =>

6. Rejoice!

6.歡喜！

6. Rejoice!

6.歡喜！

6. Rejoice!No => Make it D.R.Y, then rejoice!

6.歡喜！ 否 =>使其干燥，然后高興！

Analyze time complexity any and all times you are trying to solve a problem. It’ll make you a better developer in the log run. Your teammates and users will love you for it.

您嘗試解決問題的所有時間都要分析時間復雜度。 它可以使您成為日志運行中更好的開發人員。 您的隊友和用戶將為此而愛您。

Again, most problems you will face as programmer — whether algorithmic or programmatic — will have tens if not hundreds of ways of solving it. They may vary in how they solve the problem, but they all still solve that problem.

同樣，您將以編程人員的身份遇到的大多數問題，無論是算法上還是程序上的問題，都有數十種甚至數百種解決方法。 他們解決問題的方式可能有所不同，但是他們仍然都能解決問題。

You could be making decisions between whether to use sets or graphs to store data. You could be deciding whether or not to use Angular, React, or Backbone for a team project. All of these solutions solve the same problem in a different way.

您可能在決定使用集還是使用圖來存儲數據之間做出決定。 您可能正在決定是否為團隊項目使用Angular，React或Backbone。 所有這些解決方案都以不同的方式解決了相同的問題。

Given this, it’s hard to say there is a single “right” or “best” answer to these problems. But it is possible to say there are “better” or “worse” answers to a given problem.

鑒于此，很難說對這些問題有一個“正確”或“最佳”答案。 但是可以說，對于給定的問題有“更好”或“更差”的答案。

Using one of our previous examples, it might be better to use React for a team project if half your team has experience with it, so it’ll take less time to get up and running.

使用我們之前的示例之一，如果您的團隊有一半的經驗，將React用于團隊項目可能會更好，因此啟動和運行將花費更少的時間。

The ability to describe a better solution usually springs from some semblance of time complexity analysis.

描述更好的解決方案的能力通常源于某種時間復雜度分析。

In short, if you’re going to solve a problem, solve it well. And use some Big-O to help you figure out how.

簡而言之，如果您要解決問題，請很好地解決。 并使用一些Big-O來幫助您找出方法。

Here’s a final recap:

這是最后的總結：

• O(1) — Constant Time: it only takes a single step for the algorithm to accomplish the task.

  O(1)—恒定時間：算法僅需一步即可完成任務。

• O(log n) — Logarithmic Time: The number of steps it takes to accomplish a task are decreased by some factor with each step.

  O(log n)-對數時間：完成一項任務所需要執行的步驟數，每一步都會減少一些。

• O(n) — Linear Time: The number of of steps required are directly related (1 to 1).

  O(n)—線性時間：所需步驟數直接相關(1到1)。

• O(n2) — Quadratic Time: The number of steps it takes to accomplish a task is square of n.

  O(n2)—二次時間：完成一項任務所需的步驟數為n的平方。

• O(C^n) — Exponential: The number of steps it takes to accomplish a task is a constant to the n power (pretty large number).

  O(C ^ n)—指數：完成一項任務所需的步驟數是n次冪的常數(非常大的數字)。

And here are some helpful resources to learn more:

以下是一些有用的資源，以了解更多信息：

• Wikipedia

  維基百科

• The Big O Cheat Sheet is a great resource with common algorithmic time complexities and a graphical representation. Check it out!

  Big O備忘單是一個很好的資源，具有常見的算法時間復雜度和圖形表示形式。 看看這個！

翻譯自: https://www.freecodecamp.org/news/time-is-complex-but-priceless-f0abd015063c/

算法復雜度的表示法