Data Structure [Elementary]–Time Complexity and Space Complexity

Table of Contents

I. Introduction

1. What is a data structure?

(1) Concept

2. What is an algorithm?

1. Concept

2. Time complexity and space complexity of the algorithm

1. Algorithm efficiency

(1)Complexity of algorithm

2. Time complexity

(1) Concept

(2) Big O asymptotic representation

(3) Common time complexity calculation examples

① Calculate the time complexity of Func2

② Calculate the time complexity of Func3

③Calculate the time complexity of Func4

④ Calculate the time complexity of BubbleSort

⑤Calculate the time complexity of BinarySearch

⑥Time complexity of calculating factorial recursion Fac

⑦ Calculate the time complexity of Fibonacci sequence recursion Fib

3. Space complexity

(1) Concept

(2) Common space complexity examples

① Calculate the space complexity of BubbleSort

② Calculate the space complexity of Fibonacci (return the first n terms of the Fibonacci sequence)

③Calculate the space complexity of factorial recursion Fac

④ Calculate the space complexity of Fibonacci (return the first n terms of the Fibonacci sequence)

3. Summary

---

1. Foreword

1. What is data structure

(1)concept

Data structure is the way computers store and organize data. It refers to a collection of data elements that have one or more specific relationships with each other.

2. What is an algorithm

1. Concept

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.

2. Time complexity and space complexity of the algorithm

1. Algorithm efficiency

(1)Complexity of algorithm

• After the algorithm is written into an executable program, it requires time resources and space (memory) resources to run. Therefore, the 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.

2. Time complexity

(1)Concept

Definition of time complexity: In computer science, the time complexity of an algorithm is a function that 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 time complexity of the algorithm.

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

• Example

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);
}

The first for loop: count is executed N*N times

The second for loop: count is executed 2N times

The third for loop: count is executed 10 times

So the number of basic operations performed by Func1: F(N)=N^2 + 2n + 10 times

Law. In practice, when we calculate the time complexity, we don’t actually have to calculate the exact number of executions, but only the approximate number of executions, so here we use Big O’s asymptotic representation

(2) Big O progressive representation

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

Derive the Big O method:
1. Replace all additive constants in the run time with constant 1.
2. In the modified running times function, only the highest order term is retained.
3. If the highest-order term exists and is not 1, remove the constant multiplied by this term. The result is Big O order.
After using the asymptotic representation of Big O, the time complexity of Func1 is: O(N^2)

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.

• About time complexity

There are best, average and worst cases for the time complexity of the algorithm:

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

For example: Search for a data x in an array of length N
Best case: found 1 time

Average situation: N/2 times found
Worst case: Found N times
In in practice, the general focus is on the worst operating situation of the algorithm, so the time complexity of searching for data in the array is O(N)

(3) Common time complexity calculation examples

①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);
}

The basic operation is executed 2N + 10 times. By deriving the big O-order method, we know that the time complexity is O(N).

② 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);
}

The basic operation is performed M + N times. There are two unknowns M and N, and the time complexity is O(N + M). The sizes of M and N are unknown here. If M>N, the time complexity is O(M); If M

③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 is performed 100 times. By deriving the big O-order method, the time complexity is O(1). O(1) does not represent once, but represents a constant number of times.

④ 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;
  }
}

The basic operation is executed N times at best, and (N*(N + 1)/2 times at worst. By deriving the big O-order method + time complexity, the worst time complexity is generally O(N^2).

⑤Calculate the time complexity of PartSort1

int PartSort1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
//Find small
while(left<right & amp; & amp;a[right]>=a[keyi])
{
--right;
}
//Find the big one
while (left < right & amp; & amp; a[left] < a[keyi])
{
+ + left;
}
Swap( & amp;a[left], & amp;a[right]);
}

Swap( & amp;a[left], & amp;a[right[);
return left;
}

The time complexity of executing this function is O(N).

⑤Calculate the time complexity of BinarySearch

int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
// [begin, end]: begin and end are left-closed and right-closed intervals, so there is an = sign
while (begin <= end)
{
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 time complexity of executing this function is O(logN). (When the base is 2, it can be omitted, but when the base is other, it cannot be omitted)

⑥ Time complexity of calculating factorial recursion Fac

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

The time complexity of executing this function is O(N).

• Expand

Calculate the time complexity of the following Fac function

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 of executing this function is O(N^2).

The number of times N is executed internally changes with each call: N is executed for the first time, N-1 is executed for the second time… and so on, and these calls are accumulated again, which can be seen as an arithmetic sequence, so the time complexity is O (N^2).

⑦ Calculate the time complexity of the recursive Fib of the Fibonacci sequence

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

The time complexity of executing this function is O(2^N).

3. Space complexity

(1)Concept

1. Space complexity is also a mathematical expression, which is a measure of the amount of additional storage space that an algorithm occupies temporarily during operation
2. Space complexity is not how many bytes of space the program occupies, because this is not very meaningful, so space complexity is calculated by the number of variables. The calculation rules for space complexity are basically similar to those for time complexity, and also use theBig O asymptotic notation.

Note: The stack space required when the function is running (storing parameters, local variables, some register information, etc.) has been determined during compilation, so the space complexity is mainly determined by the additional space explicitly applied for by the function at runtime. Sure.

(2) Common space complexity examples

① Calculate the space 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;
}
}

A constant amount of extra space is used, so the space complexity is O(1) .

② Calculate the space complexity of Fibonacci (return the first n terms of the Fibonacci sequence)

long long* Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n; + + i)
{
fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
}
return fibArray;
}

malloc opens up N + 1 space, so the space complexity is O(N).

③Calculate the space complexity of factorial recursion Fac

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

The space complexity of executing this function is O(N).

Recursive space complexity calculation is also space accumulation, but different spaces can be reused.

The call to a constant number of spaces opens up a constant number of spaces. So the space complexity of this function is O(N).

④Calculate the space complexity of Fibonacci (return the first n terms of the Fibonacci sequence)

long long* Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n; + + i)
{
fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
}
return fibArray;
}

The recursive call is made N times, N stack frames are opened, and each stack frame uses a constant amount of space. The space complexity is O(N).

3. Summary

When calculating time complexity, don’t just look at the number of loops, but analyze the time complexity through the main idea of the program, so that the final result will be correct. Therefore, the learning and in-depth study of programming ideas is particularly important in the future learning process.

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57062 people are learning the system