Data structure – time complexity of algorithm

Foreword

Today we start learning data structures.

So here is a question, do you know how our computers store data?

Memory and Disk are the two core media used by computers to store data.

The difference is that data structure manages data in memory. It’s fast and has live storage. For example, we have learned the address book (array sequence list), as well as linked lists, trees, hash maps, graphs, etc…

Database manages data on disk. It is slow and has no electrical storage. Permanently saved, the database also implements functions such as adding, deleting, checking, and modifying data.

1. Data is stored in memory
Advantages: fast access speed
Disadvantages: Data cannot be saved permanently

2. Save data in file
Advantages: Data is saved permanently
Disadvantages: (1) Slower than memory operations and frequent IO operations; (2) Inconvenient to query data

3. Data is saved in the database
(1) Data is permanently saved
(2) Using SQL statements, querying is convenient and efficient.
(3) Convenient data management

Simple data on the disk are stored in files, and complex files are stored in the database.

When do you need to manage data under memory and under disk?

For example, when we open WeChat on our computer and we need to add, delete, check, or modify information, this information is stored in the memory of our computer, and the information about these people cannot be found on the disk. So why does this information still exist when we turn off the computer and turn it on again?

It is essentially permanently stored on disk on Tencent’s servers.

Why isn’t it stored on our disk?

Because the disk is running too slowly. It is inconvenient to add, delete, check and modify.

1. What is a data structure?

Data Structure is the way computers store and organize data. It refers to one or more specific relationships between them.
A collection of data elements.

2. What is an algorithm?

Algorithm: It is a well-defined calculation process that takes one or a group of values as input and produces one or a group of values as output. Simply put, an algorithm is a series of calculation steps used to transform input data into output results.

3. Algorithm efficiency

3.1 How to measure the quality of an algorithm?

In C language we learned about recursion. For example, use recursion to implement the Fibonacci sequence:

long long Fib(int N)
{
    if(N < 3)
        return 1;

    return Fib(N-1) + Fib(N-2);
}

The recursive implementation of the Fibonacci sequence is very simple, but is simplicity good? So how to measure its good and bad?

We introduce the concept of “algorithmic complexity”:

3.2 Complexity of algorithm

After the algorithm is written into an executable program, it requires time resources and space (memory) resources to run. ThereforeThe quality of an algorithm is generally measured from two dimensions: time and space, namely time complexity and space complexity.

Time complexity mainly measures how fast an algorithm runs, while space complexity mainly measures the extra space required to run an algorithm. In the early days of computers, computers had very little storage capacity. So we care a lot about space complexity. However, after the rapid development of the computer industry, the storage capacity of computers has reached a very high level. So we no longer need to pay special attention to the space complexity of an algorithm. Therefore, in practice, we talk more about time complexity, that is, the efficiency and speed of program operation.

4. Time complexity

4.1 The concept of time complexity

Definition of time complexity: In computer science,
The time complexity of an algorithm is a function
, which quantitatively describes the running time of the algorithm. The time it takes to execute an algorithm cannot be calculated theoretically. You can only know it if you put your program on the machine and run it.

But do we need to test every algorithm on a computer? It is possible to test everything on a computer, but this is very troublesome, so the time complexity analysis method is introduced. The time an algorithm takes is proportional to the number of executions of its statements. The number of executions of basic operations in an algorithm is the algorithm
Time complexity.

That is: find a certain basic statement and problem size
N
The mathematical expression between is the time complexity of the algorithm.

Please calculate
Func1
middle
+ + count
How many times was the statement executed in total?

void Func1(int N)
{
int count = 0;
for (int i = 0; i < N; + + i)
{
for (int j = 0; j < N; + + j)
{
+ + count;
}
}

for (int k = 0; k < 2 * N; + + k)
{
+ + count;
}
int M = 10;
while (M--)
{
+ + count;
}
printf("%d\
", count);
}

Func1
Number of basic operations performed:

  • N = 10 F(N) = 130
  • N = 100 F(N) = 10210
  • N = 1000 F(N) = 1002010

In practice, when we calculate the time complexity, we do not actually have to calculate the exact number of executions, but only need
Approximate number of executions, then this
Here we use large
O
Progressive representation of.

4.2 Asymptotic representation of Big O

The BigOnotation (Big O notation): is a mathematical notation used to describe the asymptotic behavior of a function .

Derivation of the Big O-order method:

Replace all additive constants in runtime with the constant 1. All constants are O(N)
In the modified number of runs function, only the highest order terms are retained. (Take the decisive term).
If the highest-order term is present and is not 1, remove the constant multiplied by this term. The result obtained is the big O order.

After using Big O’s asymptotic representation, the time complexity of Func1 is:

O(N2)

N = 10 F(N) = 100

N = 100 F(N) = 10000

N = 1000 F(N) = 1000000

Through the above, we will find that Big O’s asymptotic representation removes items that have little impact on the results and expresses the number of executions concisely and clearly.

【Expectation Management Method】

In addition, there are best, average and worst cases for the time complexity of some algorithms.
Worst case: maximum number of runs for any input size (upper bound)
Average case: expected number of runs for any input size
Best case: minimum number of runs (lower bound) for any input size
In practice, the general concern is the worst operating situation of the algorithm, so the time complexity of searching for data in the array is O(N).

Note:

Double nested loops are not necessarily O(N^2)! ! ! Find the time complexity based on your thoughts.

4.3 Common time complexity calculation examples

Example 1

Please calculate how many times the + + count statement in Func1 has been executed in total?

void Func1(int N)
{
int count = 0;
for (int i = 0; i < N; + + i)
{
for (int j = 0; j < N; + + j)
{
+ + count;
}
}
for (int k = 0; k < 2 * N; + + k)
{
+ + count;
}
int M = 10;
while (M--)
{
+ + count;
}
printf("%d\
", count);
}

After using the asymptotic representation of Big O, the time complexity of Func1 is

O(N2)

Example 2

Calculate the time complexity of Func2?

void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N; + + k)
{
+ + count;
}
int M = 10;
while (M--)
{
+ + count;
}
printf("%d\
", count);
}

Example 3

Calculate the time complexity of Func3?

void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; + + k)
{
+ + count;
}
for (int k = 0; k < N; + + k)
{
+ + count;
}
printf("%d\
", count);
}

Example 4

Calculate the time complexity of Func4?

void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; + + k)
{
+ + count;
}
printf("%d\
", count);
}

The basic operation of Example 4 was executed 10 times. By deriving the big O-order method, the time complexity is O(1).

O(1) does not represent 1 time, it represents a constant time.

Example 5

Time complexity of calculating strchr?

const char * strchr ( const char * str, int character );

strchr is a standard C library function that finds the first occurrence of a specified character in a string.

In Example 5, the basic operation is performed once at best and N times at worst. The time complexity is generally O(N) at the worst.

Example 6

Calculate the time complexity of BubbleSort?

void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; + + i)
{
if (a[i - 1] > a[i])
{
Swap( & amp;a[i - 1], & amp;a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

Maybe you would just write O(N2). Does a two-level loop have to be O(N2)?

Not really. We need to learn: Calculate time complexity mentally.

Analyzing the code, we can know that this is a bubble sorting method. The first pass is exchanged n-1 times, the second pass is exchanged n-2 times…, there are a total of

n-1 times, the n-1th time is exchanged once, so there is a total of (((n-1) + 1)(n-1))/2 = n(n-1)/2. It can be viewed as O(N2).

Left and right traverse the array together, so the time complexity is O(N).

Example 7

Calculate time complexity of BinarySearch? (Time complexity of binary search)

[About binary search]: http://t.csdnimg.cn/8Qwsf

int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
while (begin <= end) // Because begin and end are left-closed and right-closed intervals, there is an = sign.
{
int mid = begin + ((end - begin) >> 1);
if (a[mid] < x)
begin = mid + 1;
else if (a[mid] > x)
end = mid - 1;
else
return mid;
}
return -1;
}

The best thing is to find it right away,

The worst case scenario is that it is found when there is only one value left at the end or is not found at all.

Note: Time complexity refers to the number of calls

Under normal circumstances, the subscript 2 of log can be omitted, that is, it can be abbreviated to O(logN). Only the subscript 2 can be abbreviated like this.

In some books and blogs, the abbreviation is lgN. It is not recommended to write it this way, because in mathematics, lg is 10 in the table below.

The prerequisite that binary search can be used is that it must be an ordered array. Binary search has great advantages over brute force search (direct search). But the premise is that it is orderly, and it will be troublesome to add, delete, check and modify the module later. In the future, we will study AVL tree Red-black tree Hash table and so on to solve such problems.

Example 8

Time complexity of computing factorial recursion Fac.

long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}

The time complexity is O(N) .

Recursive calls are the accumulation of multiple calls.

Each recursive call is O(1) , superimposed N + 1 times, that is, O(N).

Example 8 Transformation

Time complexity of computing factorial recursion Fac.

long long Fac(size_t N)
{
if (0 == N)
return 1;
for (size_t i = 0; i < N; + + i)
{
//.....
}
return Fac(N - 1) * N;
}

The time complexity is O(N2). ((N + 0)(N + 1))/2

Recursively call N times, the value of each call is uncertain, from N->0. The cumulative number of recursions is an arithmetic sequence.

Example 9

Calculate the time complexity of Fibonacci recursion Fib.

long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}

The time complexity is O(2^N).

Finally, use the geometric series to calculate the total The number of calls is enough.

The dislocation subtraction method is used when summing here, which will not be explained in detail here.

http://t.csdnimg.cn/bCH04

Referring to this article, we use iteration to solve the Fibonacci sequence problem. Its time complexity is O(N), which is better than recursion. The recursive method for summing Fibonacci numbers is simple in idea, but has little practical significance. Because its time complexity is too high. (Exponential explosion function!)

5 Singles

Only one number appears once in an array, all other numbers appear in pairs. Write a function to find this number.

[Method 1] Violent solution: count the number of times each element appears, and then find the one that only appears once.

【Method 2】XOR

XOR operator: same as 0, different as 1

  • a^a=0
  • a^0=a
  • a^b^a=a^a^b=b (XOR supports commutative law)
#include<stdio.h>
int main()
{
int arr[] = { 1,2,3,4,5,6,1,2,3,4,5 };
int sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
int ret = 0;
for (i = 0; i < sz; i + + )
{
ret ^= arr[i];
}
printf("%d ", ret);
return 0;
}

The output is 6.

Single Dog 2

Only two numbers in an array appear once, and all other numbers appear twice. Write a function to find these two numbers that appear only once.

[Method 1] Violent solution

[Method 2] Grouped XOR

Idea:

Grouping: Divide the two singles into two groups, and then use the singleton 1 XOR method to solve them separately.

First, XOR all the elements of the array together, and the result obtained is the result of the XOR of two singletons.
Because the two singles must be different, the result of XOR must not be 0. According to the principle that the same is 0 and the difference is 1, the binary bits in the result must have 1, and the number of digits that are 1 is selected for grouping. In this way, two singles can be placed in different groups.
As long as the result after XOR is 1, it can be used for grouping
If & amp;1 == 1, then this bit is 1. If & amp;1 == 0, then this bit is 0.

#include<stdio.h>
int main()
{
int arr[] = { 1,2,3,4,6,1,2,3,4,5 };//5 6
int sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
int ret = 0;
//1. All^ together
for (i = 0; i < sz; i + + )
{
ret ^= arr[i];
}
//2. Find n bits that are 1
int n = 0;//n is the number of digits equal to 1
for (n = 0; n < 32; n + + )//4 bytes 32 bits
{
if (((ret>>n) & amp; 1 )== 1)
{
break;//n is the number to move and the number to which
}
}
//3.Group
int r1 = 0;
int r2 = 0;
for (i = 0; i < sz; i + + )
{
if (((arr[i] >> n) & amp;1) == 1)
{
r1 ^= arr[i];
}
if (((arr[i] >> n) & 1) == 0)
{
r2 ^= arr[i];
}
}
printf("r1=%d r2=%d\
", r1, r2);
//Return subscript
int j = 0;
for (j = 0; j < sz; j + + )
{
if (arr[j] == r1)
printf("r1 subscript: %d\
", j);
if (arr[j] == r2)
printf("r2 subscript: %d\
", j);
}
return 0;
}
//Encapsulated into a function-----I want to bring two singles back-----use pointers
//Return subscript-----------Traverse it once

6 Disappearing Number

The array nums contains all integers from 0 to n, but one is missing. Please write code to find the missing integer. Is there any way you can do it in O(n) time? Start writing.

[Method 1] Violent solution: first bubble sort, then traverse again. The current value + 1 is not equal to the next value. This is the disappearing number.

Bubble sort time complexity: O(N^2) Traversal time complexity: O(N). Time complexity: O(N^2)

【Method 2】XOR

First loop time complexity: O(N) Second loop time complexity: O(N + 1) Time complexity: O(N)

int missingNumber(int* nums, int numsSize){
    int ret=0;
    int i=0;
    for(i=0;i<numsSize;i + + )//XOR all the arrays first. 0~N is missing a number, so it is N + 1-1 numbers, that is, N numbers.
    {
        ret^=nums[i];
    }
    for(i=0;i<=numsSize;i + + )//The result obtained is XOR again 0~N numbers 0~N has N + 1 numbers
    {
        ret^=i;
    }
    return ret;
}

[Method 3] Arithmetic sequence formula calculation: Calculate the sum of 0~N arithmetic sequence formula, subtract the elements in the array again, and the remaining numbers are the disappearing numbers.

  • Arithmetic sequence time complexity: O(1) Loop time complexity: O(N) Time complexity: O(N)
int missingNumber(int* nums, int numsSize)
{
    int N = numsSize;
    int ret=((0 + N)*(N + 1))/2; //0~N has N + 1 numbers!
    int i=0;
    for(i=0;i<numsSize;i + + )
    {
        ret-=nums[i];
    }
    return ret;
}