Space complexity calculation super full sorting!! (calculation of hand tearing complexity

  Take on the above ： Algorithm efficiency and time complexity (8 Bar message ) Time complexity calculation is super complete ！！（ The first step of data structure and Algorithm _vpurple__ The blog of -CSDN Blog

---

Catalog

0. Preface

1. Spatial complexity

1.1 Big O The progressive representation of

1.2 Give several examples of computing space complexity

1.2.1 Calculate the spatial complexity of bubble sorting

1.2.1 Computing the time complexity of factorial recursion

 1.2.3 Calculate the space complexity of fiboracci sequence realized by array and variables

 1.2.4 Calculate the space complexity of fiboracci number realized by recursion

2. Comparison of common complexity

---

---

0. Preface

In contrast, current algorithms pay less attention to spatial complexity , Because the storage space of current devices is relatively large .

1GB=1024*1024*1024 byte    

1GB Probably 10 Gigabytes

1MB Probably 100 Ten thousand bytes

1GB=1024MB   1MB=1024KB   1KB=1024 byte

---

1. Spatial complexity

Spatial complexity is also a mathematical expression , Is an algorithm in the process of running A measure of the amount of storage space temporarily occupied , That is, the size of the extra space .

Space complexity is not how much the program takes up bytes Space , Because it doesn't make much sense either , So the spatial complexity is Number of variables .

Spatial complexity calculation rules are basically similar to practical complexity , Also use large O Progressive representation .

Be careful ： Stack space required for function runtime ( Store parameters 、 local variable 、 Some register information, etc ) It has been determined during compilation , Therefore, the spatial complexity is mainly determined by the additional space explicitly requested by the function at run time .

---

1.1 Big O The progressive representation of

Big O Symbol （Big O notation）： Is a mathematical symbol used to describe the progressive behavior of a function .

O() The number in brackets is more about this The magnitude of the algorithm , Big O It's an estimate , Not the exact number of executions .

Derivation is great O Order method ：

1、 With constant 1 Replace all the addition constants in runtime .

2、 In the modified run times function , Only the highest order terms .

3、 If the coefficient of the highest order term exists and is not 1, The constant multiplied by this item is removed . The result is big O rank .

---

1.2 Give several examples of computing space complexity

1.2.1 Calculate the spatial complexity of bubble sorting

//  Calculation BubbleSort Spatial complexity of ？
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(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}

The spatial complexity of bubble sorting is ：O(1)

The analysis is as follows ：

1.2.1 Computing the time complexity of factorial recursion

//  Compute factorial recursion Fac Spatial complexity of ？
long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}

  The time complexity of factorial recursion ：O(N).

The analysis is as follows ：

 1.2.3 Calculate the space complexity of fiboracci sequence realized by array and variables

//  Calculation Fibonacci Spatial complexity of ？
//  Returns the first of the Fibonacci sequence n term 
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;
}

Realize the spatial complexity of fiboracci sequence with array ：O(N).

Using three variables to calculate the spatial complexity of fiboracci sequence back and forth is ：O(N).

 1.2.4 Calculate the space complexity of fiboracci number realized by recursion

//  Compute Fibonacci recursion Fib Time complexity of ？
long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

The space complexity of fiboracci number realized by recursion ：O(N).

First, calculate how to call two functions repeatedly in the main function , The space occupied by the function .

 

 

Space can be reused .

Give space back to the operating system , The release of the , Instead of destroying , Just give the right of use to the operating system

The spatial complexity is basically O(1) perhaps O(N), Other spatial complexities are uncommon . Suppose you open a N*N Array of , Then its spatial complexity is O(N^2). Structure does not discuss the number of structures , Just look at the whole . Don't look at the details , Just look at the magnitude .

---

2. Comparison of common complexity

The common complexity of general algorithms is as follows ：

The lower the table, the higher the complexity

5201314	O(1)	Constant order
3log(2)n+4	O(log(2)n)	Logarithmic order
3n+4	O(n)	Linear order
2n+3nlog(2)n+14	O(nlog(2)n)	nlogn rank
3n^2+4n+5	O(n^2)	Square order
4n^3+3n^2+4n+5	O(n^3)	Cubic order
2^n	O(2^n)	Exponential order

The legend is as follows （ The picture comes from Baidu ）：

 

Please note that ：  And logN It is equivalent. .

---

Hello ！ This is Yuanzai , I hope this summary of spatial complexity is helpful to you , Follow my column 《 The way to advance the data structure ——— Hard version 》, This column will also update the data structure related content synchronously , I hope it helped you , I also hope to communicate with you more , Common progress ！！ I wish you happy every day ^-^, Yuanzai goes to the liver for the next article ~~