当前位置:网站首页>Time complexity & space complexity

Time complexity & space complexity

2022-07-07 04:52:00 ᝰꫛꪮꪮꫜ*

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 :

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA4Z2w6qub6qqu6qqu6qucKg==,size_20,color_FFFFFF,t_70,g_se,x_16

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)

 

 

原网站

版权声明
本文为[ᝰꫛꪮꪮꫜ*]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/02/202202130742057699.html