Time Complexity -mycodeschool

简介: Time Complexity - why should we care?How to analyze Time Complexity?Time Complexity analysis - asymptotic notations.Time Complexity analysis -some general rules.

Time Complexity - why should we care?

n is a prime?

A

B

for 2 to n-1 if i divides n n is not prime

for 2 to sqrt(n) if i divides n n is not prime

this takes (n-2) times

this takes (sqrt(n)-1) times

with the increasing of the number n,B is faster than A.


How to analyze Time Complexity?

Input -rate of growth of time

we suggest a model machine:

single processor

32bit

sequential execution

1 unit time for arithmetical and logical operations

1 unit for assignment and return

O is an Asymptotic notation(渐进符号)

Tsum = k O(1)

Tsumoflist = Cn + C| O(n)

Tsumofmatrix = Cn2 +C|n +C|| O(n2)


Time Complexity analysis - asymptotic notations

O -"big -on" notation -> upper bound

O(g(n))={f(n):there exist constants C and n0 ,f(n)<=Cg(n),for n>=n0}

eg:

f(n) = 5n2 +2n + 1

g(n) = n2 C=5+2+1=8 n0 = 1

f(n)<=8n2 , n>=1

image-20230421174825660.png

Ω - Omega notation->lower bound

Ω(g(n)) = {f(n):there exist constants C and n0 Cg(n)<=f(n),for n>=n0}

eg:

f(n) = 5n2 +2n + 1

g(n) = n2 C=5 n0 = 0

5n2<=f(n) , n>=0

image-20230421175723383.png

θ - Theta notation -Tight bound

θ(g(n)) = {f(n):there exist constants C1 ,C2 and n0 ,C1g(n)<=f(n)<=C2g(n),for n>=n0}

f(n) = 5n2 +2n +1

g(n) = n2

C1 =5 C2 =8 n0 =1

5n2 <= f(n) <=8n2,n>=1

image-20230421180844410.png


Time Complexity analysis -some general rules

We analyze time complexity for:

Very large input-size

Worst case scenari0

Rule:

drop lower order terms

drop constant multiplier

eg:

T(n) = 17n4 + 3n3 + 4n +8-> T(n) = n4 ->O(n4)

Rule:Running Time = the sum of running time of all garments

in a program:

simple statements fragment1 O(1)

signal loop fragment2 O(n)

nested loop fragment3 O(n2)

it takes O(n2)

if we use if fragment2 O(n) else fragment3 O(n2) ,it also takes O(n2)

we always try to analyze it in the worst case

Rule: conditional statements, Pick complexity of condition which is worst case

 

目录
打赏
0
0
0
0
0
分享
相关文章
使用Python实现Hull Moving Average (HMA)
赫尔移动平均线(Hull Moving Average,简称HMA)是一种技术指标,于2005年由Alan Hull开发。它是一种移动平均线,利用加权计算来减少滞后并提高准确性。
485 0
YOLOv7: Trainable bag-of-freebies sets new state-of-the-art for real-time object detectors
YOLOv7在5 FPS到160 FPS的范围内,在速度和精度方面都超过了所有已知的物体检测器,在GPU V100上以30 FPS或更高的速度在所有已知的实时物体检测器中具有最高的精度56.8% AP。
544 0
PAT (Advanced Level) Practice - 1145 Hashing - Average Search Time(25 分)
PAT (Advanced Level) Practice - 1145 Hashing - Average Search Time(25 分)
131 0
PAT (Advanced Level) Practice - 1096 Consecutive Factors(20 分)
PAT (Advanced Level) Practice - 1096 Consecutive Factors(20 分)
164 0
PAT (Advanced Level) Practice - 1079 Total Sales of Supply Chain(25 分)
PAT (Advanced Level) Practice - 1079 Total Sales of Supply Chain(25 分)
162 0
Speed Matters: How To Process Big Data Securely For Real-time Applications
Big Data processing has stepped up to provide organizations with new tools and technologies to improve business efficiency and competitive advantage.
1343 0
Speed Matters: How To Process Big Data Securely For Real-time Applications
Real-time Monitoring and Alerts for Senior Citizens - Big Data for Healthcare
This article discusses Alibaba Cloud PostgreSQL best practices for healthcare applications. In particular, we will explore how Big Data can be applied.
2559 0
Real-time Monitoring and Alerts for Senior Citizens - Big Data for Healthcare
Effective Objective-C 2.0
本书是iOS开发进阶的必读书籍之一。文中部分名词的中文翻译略坑,比如对block和GCD的翻译。其他整体还好,原作者写的比较用心。代码规范讲了不少,底层原理讲了一点点,且主要集中在第二章。
1425 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等