Time complexity & space complexity

Ha ha ha ha , Let's talk nonsense first , Today I know how to add emoticons to the content , Um. , So I gave it a try , So happy 🥰🤪🧨

【 Preface 】

•   Time complexity mainly measures the running speed of an algorithm
• Spatial complexity mainly measures the additional space required by an algorithm

In the early days of computer development , The storage capacity of the computer is very small . So I care about space complexity . But after the rapid development of the computer industry , The storage capacity of the computer has reached a high level . So now we don't need to pay special attention to the spatial complexity of an algorithm . 

Catalog

Time complexity

Spatial complexity

‍️‍️‍️ Problem practice

---

Time complexity

1. The number of times the basic operations in the algorithm are executed , Time complexity of the algorithm

2. We use it Big O Progressive method Time complexity （ We can understand it as the approximate number of executions ）

• With constant 1 Replace all the addition constants in runtime .
• In the modified run times function , Only the highest order terms .
• If the highest order term exists and is not 1, The constant multiplied by this item is removed
• The result is big O rank

‍️ For example, the following code block ：

Two for Loop plus one while loop , Execution times are N^2 + 2* N + 10

Big use O Progressive method , Keep only the highest order and use 1 Instead of constants , Therefore, the time complexity of this function is O（N^2)

 

• Usually, the time complexity of recursive algorithm is 0（N）

     （ But what? , Recursion of Fibonacci sequence , The time complexity is O（2^N))

• Every time *n perhaps /n operation , The general time complexity is O（log n), For example, binary search is

    （ The fourth question of Li Kou just done today , It clearly limits the time complexity of the algorithm to  O(log (m+n)), So sad , I didn't expect to use two points , Specially, I'll sort out the time complexity Topic link ： Find the median of two positive arrays - Power button （LeetCode） (leetcode-cn.com)）

---

Spatial complexity

1. Space complexity is a measure of the amount of storage space temporarily occupied by an algorithm during operation

！！！ Yes. Additional development Array space size of , It's not how much the program takes bytes Space of oh

2. The space complexity is also large O Progressive method , No more details

Usually , The space complexity of recursion is also O（n)

---

‍️‍️‍️ Problem practice

Time complexity ：

1.

int binarySearch(int[] array, int value) {  int begin = 0;  int end = array.length - 1;  while (begin <= end) {    int mid = begin + ((end-begin) / 2);    if (array[mid] < value)      begin = mid + 1;    else if (array[mid] > value)      end = mid - 1;    else      return mid;  }  return -1;}

【 answer 】O(logN)        Two points search

2.

long factorial(int N) {return N < 2 ? N : factorial(N-1) * N;}

【 answer 】 Time complexity The space complexity is O(N)    recursive N Time

3.

int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);}

【 answer 】O(2 ^ N)