当前位置:网站首页>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
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)
边栏推荐
- Break the memory wall with CPU scheme? Learn from PayPal to expand the capacity of aoteng, and the volume of missed fraud transactions can be reduced to 1/30
- 窗口可不是什么便宜的东西
- 深耕开发者生态,加速AI产业创新发展 英特尔携众多合作伙伴共聚
- 【ArcGIS教程】专题图制作-人口密度分布图——人口密度分析
- 程序员上班摸鱼,这么玩才高端!
- Intel and Xinbu technology jointly build a machine vision development kit to jointly promote the transformation of industrial intelligence
- DFS和BFS概念及实践+acwing 842 排列数字(dfs) +acwing 844. 走迷宫(bfs)
- Windows are not cheap things
- leetcode 53. Maximum Subarray 最大子数组和(中等)
- Up to 5million per person per year! Choose people instead of projects, focus on basic scientific research, and scientists dominate the "new cornerstone" funded by Tencent to start the application
猜你喜欢
Tree map: tree view - draw covid-19 array diagram
Programmers go to work fishing, so play high-end!
【736. Lisp 语法解析】
What if the win11 screenshot key cannot be used? Solution to the failure of win11 screenshot key
深耕开发者生态,加速AI产业创新发展 英特尔携众多合作伙伴共聚
Analyse approfondie de kubebuilder
AI landing new question type RPA + AI =?
The request request is encapsulated in uni app, which is easy to understand
R语言主成分pca、因子分析、聚类对地区经济研究分析重庆市经济指标
Case reward: Intel brings many partners to promote the innovation and development of multi domain AI industry
随机推荐
Code source de la fonction [analogique numérique] MATLAB allcycles () (non disponible avant 2021a)
sscanf,sscanf_ S and its related usage "suggested collection"
R descriptive statistics and hypothesis testing
A series of shortcut keys for jetbrain pychar
ACL2022 | 分解的元学习小样本命名实体识别
If you ask me about R code debugging, I will tell you head, STR, help
Common Oracle SQL statements
九章云极DataCanvas公司摘获「第五届数字金融创新大赛」最高荣誉!
Introduction to namespace Basics
食堂用户菜品关系系统(C语言课设)
九章云极DataCanvas公司蝉联中国机器学习平台市场TOP 3
JS also exports Excel
指针与数组在函数中输入实现逆序输出
Read of shell internal value command
《原动力 x 云原生正发声 降本增效大讲堂》第三讲——Kubernetes 集群利用率提升实践
Chapter 9 Yunji datacanvas was rated as 36 krypton "the hard core technology enterprise most concerned by investors"
軟件測試之網站測試如何進行?測試小攻略走起!
Analyse approfondie de kubebuilder
Basic idea of counting and sorting
一图看懂!为什么学校教了你Coding但还是不会的原因...