大o记号

Is it just enough to know how to program? Is logic the only requirement?

仅仅知道如何编程就足够了吗？ 逻辑是唯一的要求吗？

The knowledge of basic data structures, their characteristics, and the algorithms are important tools in a software engineer’s toolkit. Having the right tools for the job can make the job a lot easier. Being trained in the proper use of these tools is essential for being effective. Data structures and algorithms allow you to write performant code, which minimizes the use of scarce resources and helps ensure that your code is not just correct but also fast.

基本数据结构，其特征和算法的知识是软件工程师工具包中的重要工具。 拥有正确的工作工具可以使工作轻松得多。 正确使用这些工具的培训对于有效至关重要。 数据结构和算法使您可以编写高效的代码，从而最大程度地减少了稀缺资源的使用，并有助于确保代码不仅正确而且快速。

If you have participated in Google Kickstart or solved some Hacker Rank contests or others, you would have encountered a situation where your code might be slower than expected and possibly you got a check popup or warning saying your code couldn’t do it on time. In the same way, we compare different algorithms based on their elapsed time, space used and network bandwidth used. These will say either your code is performant or not. These are called Dimensions of Performance.

如果您参加了Google Kickstart或解决了一些Hacker Rank竞赛或其他竞赛，您可能会遇到这样的情况，即您的代码可能比预期的要慢，并且可能会弹出检查窗口或警告说您的代码无法按时完成。 同样，我们根据不同的算法经过时间，使用的空间和使用的网络带宽来比较它们。 这些将说明您的代码是否有效。 这些称为性能维度。

Now that we know complexity is a measure of performance, how to measure complexity?

既然我们知道复杂度是性能的度量，那么如何度量复杂度？

The complexity of your code, whether it’s time complexity, space complexity, or the complexity for any other resource usage, can be expressed in terms of the Big-O notation.

代码的复杂性，无论是时间复杂性，空间复杂性，还是任何其他资源使用的复杂性，都可以用Big-O表示法来表示。

Now let us try to know about different types of complexities.

现在让我们尝试了解不同类型的复杂性。

1.恒定的复杂性 (1. Constant Complexity)

Real-life Example: Suppose I am selecting some people for a game and I will select only first four applicants. Will the number of applicants effect complexity of selection?

实际示例：假设我选择了一些人参加游戏，而我只会选择前四个申请者。 申请人数会影响选择的复杂性吗？

Even if there 1000 applicants I will just ignore the rest and select only the first four people. So the complexity is O(4).

即使有1000个申请人，我也只会忽略其余的，而只会选择前四个人。 因此复杂度为O(4)。

Programming Example: If we create a function which will take an array as input and display the first character of the array. The program will have the complexity of O(1). This is because even if we take a 1,000,000 longword we only care about the first letter.

编程示例：如果我们创建一个将数组作为输入并显示数组第一个字符的函数。 该程序将具有O(1)的复杂度。 这是因为即使我们采用一百万个长字，我们也只关心第一个字母。

Example code:

示例代码：

//C++ Code

// C ++代码

#include <iostream> using namespace std;

#include <iostream> 使用命名空间std;

int main() { char str[1000000]; cout << “Enter Your Name::”; cin.getline(str, 1000000);

int main() { char str [1000000]; cout <<“输入您的姓名：：”； cin.getline(str，1000000);

cout << “\nFirst Letter is:: “ << str[0]; return 0; }

cout <<“ \ n第一个字母是：:” << str [0]; 返回0; }

So if complexity doesn’t change with the number of inputs it is called Constant Complexity

因此，如果复杂度不随输入数量而变化，则称为恒定复杂度

2.对数复杂度(2. Logarithmic Complexity)

Real-life Example: In your school days, there was a custom of allowing benches for each person. Here what is done is everyone is made to stand according to increasing order of heights. Then they will be made to sit one after the other.

现实生活中的例子：在您上学的日子里，习惯上允许每个人都有长凳。 在这里要做的是使每个人都按照高度的增加顺序站起来。 然后他们将被一个接一个地坐着。

Now, suppose a person who was out for some reason comes in. He is the member of your class and needs to be added in the line. So, what your lecturer would probably do is, go to the exact middle of the line and compare the heights. If he fits in then that is all, else, your teacher will only consider the taller part if he is taller than the compared person, or the other if he is short. Again, the person is compared and compared until his height finally fits somewhere. Here unlike Linear Complexity, you are not comparing with each person in the group. Instead, as every comparison halves the entire set. Here comes the next complexity called Logarithmic Complexity or O(log n).

现在，假设有一个因某种原因而外出的人进来了。他是您班上的成员，需要添加到该行中。 因此，您的讲师可能会做的是，转到直线的中间并比较高度。 如果他适合，仅此而已，否则，您的老师只有在他比被比较的人高时才考虑更高的部分，或者在他矮时才考虑另一个。 再一次，对这个人进行比较，直到他的身高终于适合某个地方。 在这里，与线性复杂度不同，您不需要与组中的每个人进行比较。 相反，因为每个比较将整个集合减半。 接下来是下一个复杂度，称为对数复杂度或O(log n)。

Programming Example: The above problem is called as searching in Programming and the method is called as Binary Search. The main condition is that the elements must be in sorted order. Here instead of heights, we will compare numbers and if the number is missing we display a message saying “not found”

编程示例：上述问题在“编程”中称为“搜索”，而该方法称为“二进制搜索”。 主要条件是元素必须按排序顺序。 在这里，我们将代替数字而不是高度，如果缺少数字，我们将显示一条消息，提示“未找到”

Example code:

示例代码：

// C++ program to implement recursive Binary Search #include <bits/stdc++.h> using namespace std;

// C ++程序实现递归二进制搜索#include <bits / stdc ++。h> 使用命名空间std;

// A recursive binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1 int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r — l) / 2;

//递归二进制搜索功能。 它返回//存在x在给定数组arr [l..r]中的位置， //否则为-1 int binarySearch(int arr []，int l，int r，int x) { 如果(r> = l){ int mid = l +(r_1)/ 2;

// If the element is present at the middle // itself if (arr[mid] == x) return mid;

//如果元素位于中间//本身如果(arr [mid] == x) 返回中间

// If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid — 1, x);

//如果element小于mid，则//它只能出现在左子数组中如果(arr [mid]> x) 返回binarySearch(arr，l，mid — 1，x);

// Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); }

//其他元素只能存在//在正确的子数组中返回binarySearch(arr，mid + 1，r，x); }

// We reach here when element is not // present in array return -1; }

//我们在元素不存在时到达此处//存在于数组中返回-1; }

int main(void) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int n = sizeof(arr) / sizeof(arr[0]); int result = binarySearch(arr, 0, n — 1, x); (result == -1) ? cout << “Element is not present in array” : cout << “Element is present at index “ << result; return 0; }

int main(无效) { int arr [] = {2，3，4，10，40}; 整数x = 10; int n = sizeof(arr)/ sizeof(arr [0]); int结果= binarySearch(arr，0，n_1，x); (结果== -1)？ cout <<“数组中不存在元素” ：cout <<“元素出现在索引“ <<结果； 返回0; }

So, if you find some program that works on half the existing set after each iteration, it will most commonly have the complexity of O(log n).

因此，如果您发现某个程序在每次迭代后都可以在现有集合的一半上工作，则该程序通常具有O(log n)的复杂度。

3.线性复杂度 (3. Linear Complexity)

Real-life Example: In your school or college days, first-class of every teacher would probably be an introduction. First, your teacher would and then he/she would ask the whole class to introduce.

现实生活中的例子：在您上学或上大学的时候，每位老师的一流水平可能是入门。 首先，您的老师会然后要求他/她向全班介绍。

Here you must notice that if the number of students is 10 it might take probably 20 minutes. If it is 1,000,000 then it probably takes around 2,000,000 minutes. Here the most important point to note is that time increases with an increase in the number of students. So here the complexity depends on the number of students and hence the complexity is O(n), which is called Linear Complexity.

在这里您必须注意，如果学生人数为10，则可能需要20分钟。 如果是1,000,000，则大概需要2,000,000分钟。 这里要注意的最重要一点是，时间随着学生人数的增加而增加。 因此，这里的复杂度取决于学生的数量，因此复杂度为O(n)，称为线性复杂度。

Programming Example:

编程实例：

If you want to traverse through an array (which is like reading a book line by line), as the number of inputs increases the output complexity increases. This is because the number of iterations increases with the increase in input.

如果要遍历数组(就像逐行阅读一本书一样)，则随着输入数量的增加，输出的复杂性也会增加。 这是因为迭代次数随着输入的增加而增加。

Example code:

示例代码：

#include <iostream>using namespace std;

#include <iostream> 使用命名空间std;

int main() { int numbers[5] = {7, 5, 6, 12, 35};

int main(){ 整数number [5] = {7，5，6，12，35};

cout << “The numbers are: “; for (const int &n : numbers) { cout << n << “ “; }

cout <<“数字是：”; 对于(const int＆n：number){ cout << n <<“”; }

cout << “\nThe numbers are: “; for (int i = 0; i < 5; ++i) { cout << numbers[i] << “ “; }

cout <<“ \ n数字是：”; 对于(int i = 0; i <5; ++ i){ cout <<数字[i] <<“”; }

return 0;}

返回0; }

So, if complexity increases proportionally to the input it is called Linear Complexity.

因此，如果复杂度与输入成比例增加，则称为线性复杂度。

4.线性运算的复杂性 (4. Linearithmic Complexity)

Real-life Example: Let us consider that in your class you were to be sorted as per your heights. Now, what I will do is, divide the whole class into 2. Then, divide these 2 groups into 2 and repeat the same with the subdivided groups until I divide the whole group into individuals. Then I start comparing a pair of 2 and arrange them according to their heights. Again, compare 2 pairs and arrange them and so on until the whole group is sorted.

真实示例：让我们考虑一下，在您的课堂上，您将按照自己的身高排序。 现在，我要做的是将整个班级划分为2个。然后，将这两个组划分为2个，然后对细分的组重复相同的操作，直到将整个组划分为多个个体为止。 然后，我开始比较两个2并根据它们的高度进行排列。 同样，比较2对并排列它们，依此类推，直到对整个组进行排序。

This way of sorting has a complexity of O(n log n) or Linearithmic Complexity.

这种排序方式的复杂度为O(n log n)或线性运算复杂度。

演示地址

Programming Example: The above-mentioned example is called binary sorting in programming, which comes under the divide and conquers method of solving a problem. Here instead of heights, we consider the value of numbers.

编程示例：上面提到的示例在编程中称为二进制排序，属于解决问题的分而治之方法。 在这里，我们不考虑高度，而是考虑数字的值。

Example code:

示例代码：

// C++ program to implement recursive Binary Search #include <bits/stdc++.h> using namespace std;

// C ++程序实现递归二进制搜索#include <bits / stdc ++。h> 使用命名空间std;

// A recursive binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1 int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r — l) / 2;

//递归二进制搜索功能。 它返回//存在x在给定数组arr [l..r]中的位置， //否则为-1 int binarySearch(int arr []，int l，int r，int x) { 如果(r> = l){ int mid = l +(r_1)/ 2;

// If the element is present at the middle // itself if (arr[mid] == x) return mid;

//如果元素位于中间//本身如果(arr [mid] == x) 返回中间

// If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid — 1, x);

//如果element小于mid，则//它只能出现在左子数组中如果(arr [mid]> x) 返回binarySearch(arr，l，mid — 1，x);

// Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); }

//其他元素只能存在//在正确的子数组中返回binarySearch(arr，mid + 1，r，x); }

// We reach here when element is not // present in array return -1; }

//我们在元素不存在时到达此处//存在于数组中返回-1; }

int main(void) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int n = sizeof(arr) / sizeof(arr[0]); int result = binarySearch(arr, 0, n — 1, x); (result == -1) ? cout << “Element is not present in array” : cout << “Element is present at index “ << result; return 0; }

int main(无效) { int arr [] = {2，3，4，10，40}; 整数x = 10; int n = sizeof(arr)/ sizeof(arr [0]); int结果= binarySearch(arr，0，n_1，x); (结果== -1)？ cout <<“数组中不存在元素” ：cout <<“元素出现在索引“ <<结果； 返回0; }

I remember this as one and a half complexity, which is like multiplying linear and logarithmic complexities.

我记得这是一个一半的复杂度，就像将线性和对数复杂度相乘。

5.多项式复杂度 (5. Polynomial Complexity)

Real-life Example: Suppose you go shopping with a long shopping list and before you go for billing you will surely like to check you have taken all the items present in the list. Now you must first check one item in the list and check if it is there in your basket, again the second item in the list and in the basket. So, you go through the same number of twice. So, the complexity is O(n²) or Quadratic Complexity.

实际示例：假设您购物时购物清单很长，并且在开始计费之前，您肯定希望检查一下是否已取出列表中所有物品。 现在，您必须首先检查列表中的一项，并检查是否在购物篮中，然后再次检查列表中和篮中的第二项。 因此，您经历两次相同的次数。 因此，复杂度为O(n²)或二次复杂度。

Programming Example:

编程实例：

Check this video to understand what is insertion sort, which is an example for the program with O(n²) Complexity.

观看此视频，了解什么是插入排序，这是具有O(n²)复杂度的程序的示例。

演示地址

Example Program:

示例程序：

// C++ program for insertion sort #include <bits/stdc++.h> using namespace std;

//用于插入排序的C ++程序#include <bits / stdc ++。h> 使用命名空间std;

/* Function to sort an array using insertion sort*/void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i — 1;

/ *使用插入排序对数组进行排序的功能* / void insertSort(int arr []，int n) { int i，key，j; 对于(i = 1; i <n; i ++) { 键= arr [i]; j = i-1；

/* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j — 1; } arr[j + 1] = key; } }

/ *移动arr [0..i-1]的元素，这些元素是比关键更大，领先一步他们当前位置的* / while(j> = 0 && arr [j]>键) { arr [j + 1] = arr [j]; j = j_1； } arr [j + 1] =键； } }

// A utility function to print an array of size n void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) cout << arr[i] << “ “; cout << endl; }

//一个实用函数，用于打印大小为n的数组void printArray(int arr []，int n) { 我对于(i = 0; i <n; i ++) cout << arr [i] <<“”; cout << endl; }

/* Driver code */int main() { int arr[] = { 12, 11, 13, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]);

/ *驱动程序代码* / int main() { int arr [] = {12，11，13，5，6}; int n = sizeof(arr)/ sizeof(arr [0]);

insertionSort(arr, n); printArray(arr, n);

insertSort(arr，n); printArray(arr，n);

return 0; }

返回0; }

Like the above-discussed complexity, you can even find O(n³), O(n⁴),… which come under Polynomial Complexity, which tends to go through each element again and again.

像上面讨论的复杂度一样，您甚至可以找到O(n³)，O(n⁴)，…，它们属于多项式复杂度，它倾向于一次又一次地遍历每个元素。

These are some of the most commonly seen complexities and there are like:

这些是一些最常见的复杂性，例如：

6. O(log²n){对数}复杂度 (6. O(log² n) {Log sqaure} Complexity)

7. O(n ^(1/2)){根n}复杂度(7. O(n^(1/2)) {Root n} Complexity)

8. O(2 ^ n){指数}复杂度(8. O(2^n) {Exponential} Complexity)

9. O(e ^ n){指数}复杂度(9. O(e^n) {Exponential} Complexity)

10. O(n！){基础}复杂性(10. O(n!) {Factorial} Complexity)

还有很多其他...(and so many others…)

I have created graphs of these 10 complexities in the below-given link. Feel free to check them out and understand the complexities in a better way.

我在下面给出的链接中创建了这10个复杂度的图表。 随时检查它们，以更好的方式了解其复杂性。

Now after looking at so many complexities you might be wondering which is better?

现在看了这么多复杂性之后，您可能会想知道哪个更好？

The order is:

顺序是：

常数<对数<对数平方<根n <线性<线性<二次方<指数(2 ^ n)<指数(e ^ n) (Constant < Logarithmic < Log square < Root n < Linear < Linearithmic < Quadratic < Exponential (2^n) < Exponential (e^n))

Here complexity increases from left to right. But this is for bigger inputs only. See the graph properly and comment below if Exponential or Quadratic would be greater for lower values of input.

在这里，复杂度从左到右增加。 但这仅用于较大的输入。 如果输入值较低，则指数或平方会更大，请正确查看该图并在下面评论。

One more important thing is, the complexity can be different for different inputs, which are called as best case, average case and worst-case complexities. When someone talks about any complexities they mean worst-case complexity.

更重要的一点是，对于不同的输入，复杂度可能有所不同，分别称为最佳情况，平均情况和最坏情况。 当有人谈论任何复杂性时，它们表示最坏情况下的复杂性。

I hope this blog was useful.

我希望这个博客对您有用。

Thank you…

谢谢…

翻译自: https://medium.com/swlh/big-o-notation-dc7c44a6b9f

大o记号