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
分享
相关文章
PAT (Advanced Level) Practice - 1145 Hashing - Average Search Time(25 分)
PAT (Advanced Level) Practice - 1145 Hashing - Average Search Time(25 分)
136 0
PAT (Advanced Level) Practice - 1096 Consecutive Factors(20 分)
PAT (Advanced Level) Practice - 1096 Consecutive Factors(20 分)
168 0
PAT (Advanced Level) Practice - 1079 Total Sales of Supply Chain(25 分)
PAT (Advanced Level) Practice - 1079 Total Sales of Supply Chain(25 分)
169 0
译《Time, Clocks, and the Ordering of Events in a Distributed System》
Motivation 《Time, Clocks, and the Ordering of Events in a Distributed System》大概是在分布式领域被引用的最多的一篇Paper了。
938 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.
1351 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.
2565 0
Real-time Monitoring and Alerts for Senior Citizens - Big Data for Healthcare
AI助理

你好,我是AI助理

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