Lecture 2: Big-Oh and Graph Review
CSC 226: Algorithms and Data Structures II Quinton Yong
quintonyong@ uvic.ca
Copyright By PowCoder代写 加微信 powcoder
Asymptotic Analysis Review
• Big-Oh (𝑶)
• Big-Omega (𝛀) • Big-Theta (𝚯)
• Little-oh (𝒐)
• Little-omega (𝝎)
Big-Oh Notation Formal Definition
Let 𝒇: N → R and 𝒈: N → R
𝒇(𝒏) is 𝑶 𝒈 𝒏 if and only if there exist a real constant 𝒄 > 𝟎 and an integer constant 𝒏𝟎 > 𝟎 such that
𝒇 𝒏 ≤𝒄⋅𝒈 𝒏 forall𝒏≥𝒏𝟎
e.g. 𝒇 𝒏 is the running time of an algorithm as a function of the input size 𝒏
Visually,thissaysthatthe𝒇𝒏 curvemusteventuallyfitunderthe𝒄𝒈𝒏 curve
We say that 𝒏𝟎 • 𝒇 𝒏 is order 𝒈 𝒏
• 𝒇𝒏 isbig-Ohof𝒈𝒏
Input Size
Running Time
Big-Oh Theorems
1. 2. 3. 4.
5. 6. 7. 8.
If𝒇(𝒏)is𝑶 𝒈 𝒏 ,then𝒂⋅𝒇(𝒏)is𝑶 𝒈 𝒏 foranyconstant𝒂>𝟎 If𝒇(𝒏)is𝑶 𝒈 𝒏 and𝒙(𝒏)is𝑶 𝒚 𝒏 ,then𝒇 𝒏 +𝒙(𝒏)is𝑶 𝒈 𝒏 +𝒚(𝒏) If𝒇(𝒏)is𝑶 𝒈 𝒏 and𝒙(𝒏)is𝑶 𝒚 𝒏 ,then𝒇 𝒏 𝒙(𝒏)is𝑶 𝒈 𝒏 𝒚(𝒏) If𝒇(𝒏)is𝑶𝒈𝒏 and𝒈𝒏 is𝑶𝒚𝒏 ,then𝒇𝒏 is𝑶𝒚𝒏
If𝒇 𝒏 =𝒂𝟎 +𝒂𝟏𝒏+ … +𝒂𝒅𝒏𝒅,where𝒅and𝒂𝒌 areconstants,then𝒇 𝒏 is𝑶(𝒏𝒅) 𝒏𝒙 is𝑶(𝒂𝒏)foranyfixed𝒙>𝟎and𝒂>𝟏
𝐥𝐨𝐠(𝒏𝒙)is𝑶 𝐥𝐨𝐠 𝒏 foranyfixed𝒙>𝟎
𝐥𝐨𝐠𝒙(𝒏)is𝑶 𝒏𝒚 foranyfixed𝒙>𝟎and𝒚>𝟎
Random Access Machine (RAM) Model
• Computational model which we use to analyze algorithms theoretically
• Consists of a CPU connected to unbounded random-access memory
• Define a set of primitive operations which take constant time
• Primitiveoperationsinclude:
• Assigningvaluestovariables
• Calling a method
• Performing arithmetic operations
• Comparingnumbers
• Indexing into an array
• Following a pointer / reference
• To analyze the running time of algorithms, we count the number of primitive operations
What is a graph?
A graph 𝑮 = (𝑽, 𝑬) consists of
• a set 𝑽 of vertices (nodes)
• acollection𝑬ofpairsofverticesfrom𝑽callededges(arcs)
Example of a graph:
𝑽 = {𝒂,𝒃,𝒄,𝒅,𝒆}
𝒂,𝒃, 𝒂,𝒃, 𝒂,𝒄, 𝒃,𝒄 , 𝒃,𝒅 , 𝒄,𝒅 , 𝒄,𝒆 ,
Undirected Edges
An undirected edge 𝒆 represents a symmetric relationship between vertices 𝒖 and 𝒗
• We write 𝒆 = {𝒖, 𝒗}, where {𝒖, 𝒗} is an unordered pair
• 𝒖and𝒗aretheendpointsoftheedge
• 𝒖isadjacentto𝒗
• 𝒆isincidentto𝒖and𝒗
• The degree of a vertex is the number of incident edges e.g.𝐝𝐞𝐠 𝒖 =4,𝐝𝐞𝐠 𝒗 =2
• Parallel edges (multi-edges): more than one edge between pairs of vertices e.g. 𝒇 and 𝒈
• Self-loop: edge that connects a vertex to itself e.g.𝒉isaselfloop.Notethat𝐝𝐞𝐠 𝒘 =3.
• Usually,wedenotethenumberofverticesby𝒏andthenumberofedgesby𝒎
Undirected Paths
A walk in a graph is a sequence of vertices 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒌 such that there exist edges 𝒗𝟏,𝒗𝟐 , 𝒗𝟐,𝒗𝟑 ,…,{𝒗𝒌−𝟏,𝒗𝒌}
𝒅 𝒆 𝒂,𝒃,𝒄,𝒅,𝒃,𝒆,𝒄
• The length of a walk is the number of edges 𝒂
• If 𝑣1 = 𝑣𝑘, the walk is closed. Otherwise, it is open.
• If no edge is repeated, it is a trail.
• Aclosedtrailisacircuit.
• If no vertex is repeated, it’s a path.
• A cycle is a path with the same start and end vertices
𝒅 𝒆 𝒂,𝒃,𝒆,𝒄
Connected Graphs
A graph is connected if every pair of vertices is connected by a path Example:
• Connectedgraph
• Disconnectedgraph
• Twoconnectedcomponents
Simple Graphs
A simple graph is a graph with no self-loops and no parallel / multi-edges
Not a simple graph :
Simple graph:
For the most part, we will only be working with simple graphs in this course.
Simple Graphs
A simple graph is a graph with no self-loops and no parallel / multi-edges
Theorem: If 𝑮 = (𝑽, 𝑬) is a graph with 𝒎 edges, then deg(𝒗) = 𝟐𝒎
Theorem: Let 𝑮 be a simple graph with 𝒏 vertices and 𝒎 edges. Then, 𝒎 ≤ 𝒏 (𝒏 − 𝟏)
Corollary: A simple graph with 𝒏 vertices has 𝑶(𝒏𝟐) edges.
Complete Graphs
A complete graph is a simple graph where every pair of vertices is connected by an edge
• The complete graph on 𝒏 vertices has exactly 𝒏(𝒏−𝟏) edges 𝟐
• The complete graph on 𝒏 vertices with one self-loop per vertex has exactly 𝒏 𝒏+𝟏 edges 𝟐
A subgraph of 𝑮 = (𝑽,𝑬) is a graph 𝑮′ = (𝑽′,𝑬′) where
• 𝑽′ isasubsetof𝑽
• 𝑬′ consists of edges {𝒖,𝒗} in 𝑬 such that both 𝒖 and 𝒗 are in 𝑽′
A spanning subgraph 𝑮′ of 𝑮 contains all vertices of 𝑮
An induced subgraph 𝑮′ of 𝑮 contains all the edges of 𝑮 that have both endpoints in 𝑮′ (i.e. no edge of 𝑮 is
missing between all the vertices in 𝑮’) 𝑮=
Trees and Forests
A (free) tree is an undirected graph 𝑻 such that • 𝑻 is connected
• 𝑻 has no cycles
A rooted tree is a trees where one vertex is designated as the root
A forest is an undirected graph without cycles (collection of disconnected trees) • The connected components of a forest are trees
Rooted Tree
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com