Algorithm Analysis

Motivation

The goal of algorithm analysis is to take a block of code and determine the asymptotic run time or asymptotic memory requirements based on various parameters.

Given an array of size n: - Merge sort requires \(\Theta(n lg n)\) time and \(\Theta(n)\) additional memory

• The asymptotic behavior of algorithms indicates the ability to scale

Suppose that we have two algorithms A and B whose runtimes are \(f_{A}(n)=\Theta(n^2)\) and \(f_{B}(n)=\Theta(n lg n)\)

For \(n=2k\)

• \[f_{A}(n)=(2k)^2=4k^2\]
• \[f_{B}(n)=2k lg 2k=2k (lg k+lg 2) = 2k(lg k+1)=2k lg k + 2k\]

For \(n=10k\)

• \[f_{A}(n)=(10k)^2=4100k^2\]
• \[f_{B}(n)=10k lg 10k=10k(lg k+lg 10)\approx 10k lg k+33.2k\]

Binary search runs in \(\Theta(lg n)\) time:

• Doubling the size n requires one additional search

Machine Instructions

Given any processor, it is capable of performing only a limited number of operations

• These operations are called instructions
• The collection of instructions is called the instruction set
  • The exact set of instructions differs between processors
  • MIPS, ARM, x86, 68k, ..
• Any instruction runs in a fixed amount of time (an integral number of CPU cycles)

An example (on the Coldfire): 0x06870000000F

• which adds 15 to the 7th data register
• As human are not good at hex, this can be programmed in assembly language as: ADDI.L#$F,D7
• Assembly language has an almost one-to-one translation to machine Instructions
  • Assembly language is a low-level programming language
• Other programming languages are higher-level:
  • Fortran, Pascal, MATLAB, Java, C++, C#, ..
• The adjective “high” refers to the level of abstraction:
  • Java, C++, and C# have abstractions such as ‘Objected Oriented’
  • MATLAB and Fortran have operations which do not map to relatively small number of machine instructions: -» 1.27^2.9 %1.27**2.9 in Fortran
• The C programming language (C++ without objects and other abstractions) can be referred to as a mid-level programming language
  • There is abstraction, but the language is closely tied to the standard capabilities
  • There is a closer relationship between operators and machine instructions

Consider the operation a+=b;

• Assume that the compiler has already has the value of the variable a in register D1 and perhaps b is a variable stored at the location stored to the single instruction: ADD(A1),D1

Operators

Because each machine instruction can be executed in a fixed number of cycles, we may assume each operation requires a fixed number of cycles

• The time required for any operator is \(\Theta(1)\) including:

Retrieving/storing variables from memory

Variable assignment	=
Integer operations	+, -, *, /, %, ++, –
Logical operations	&&, ||, !
Bitwise operations	&, |, ^, ~
Relational operations	==, !=, <, <=, =>, >
Memory allocation and deallocation	new, delete

Operations

Of these, memory allocation and deallocation are the slowest by a significant factor (e.g. 100 times slower)

• They require communication with the operation system
• This does not account for the time required to call the constructor and destructor
  • Note that after memory is allocated, the constructor is run
    • The constructor may not run in \(\Theta(1)\) time

Blocks of Operations

Each operation runs in \(\Theta(1)\) time and therefore any fixed number of operations also run in \(\Theta(1)\) time.

Blocks in Sequence

Suppose that you have now analyzed a number of blocks of code run in Sequence

int* increase_Capacity(int *_array, int _n, int _delta){
  int *array_old=_array;
  _array=new int[_n+_delta];//$\Theta(1)$

  for(int i=0;i<_n;i++){
    _array[i]=array_old[i];//$\Theta(n)$
  }

  delete [] array_old;
  return _array;//$\Theta(1)$
}

• To calculate the total run-time, add the entries: \(\Theta(1+n+1)=\Theta(n)\)

Other examples include:

• Run three blocks of code which are \(\Theta(1), \Theta(n^2)\), and \(\Theta(n)\)
• Total runtime: \(\Theta(1+n^2+n)=\Theta(n^2)\)
• Run three blocks of code which are \(\Theta(n lg(n))\), and \(\Theta(n^{1.5})\)
• Total runtime \(\Theta(n lg(n)+n^{1.5})=\Theta(n^{1.5})\)
• Recall this linear ordering from the previous topic

• When considering a sum, take the dominant term

source “K-MOOC 허재필 교수님의 <인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고> 강좌의 6-1 코드 블록 단위의 복잡도 분석 중(http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2020_T1)”

back next

Comments

Post comment

Loading...