首页 > 其他 > 详细

CS3334 Lecture 1

时间:2018-01-20 12:09:58      阅读:274      评论:0      收藏:0      [点我收藏+]

Lecture 1: Complexity Analysis

How to measure Running time: Use a function to model the running time of a program or procedure.

  • Assume an abstract machine and count the number of “steps” executed by an algorithm

 

Function: In mathematics, a function is a relation between a set of inputs and a set of allowed outputs with the property that each input is related to exactly one output

 

How to Model Running Time as a function:

技术分享图片技术分享图片

 

Compare the functions of Running Time models:

Consider the order of growth of running time, not the actual value

The order of growth rate

  • Give a simple characterization of the algorithm’s efficiency 
  • Allow us to compare the relative performance of alternative algorithms

In the analysis of algorithms, we need to consider the performance of algorithms when applied to very very big input datasets, e.g., very large n (i.e., asymptotic analysis)

TA(n) = 100n + 50

TB(n) = (0.5)n2 + 4.5n + 5

 技术分享图片TA(n) > TB(n) if n < c,   but TA(n) < TB(n) if n > c

 

Asymptotic Notation - notations to express the growth rate of a function (Just for function)

A way to compare ‘size‘ of functions:

– ο-notation (“Big-oh”) ≈≤ (upper bound)

– Ω-notation (“Big-omega”) ≈≥ (lower bound)

– θ-notation (“theta”) ≈= (in between)

 

CS3334 Lecture 1

原文:https://www.cnblogs.com/charon922/p/8320028.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!