# Data Structures

(1)

SNU

## Ch2. Performance Analysis

(2)

2

SNU IDB Lab.













(3)

SNU







(4)

4

SNU IDB Lab.













(5)

SNU





(6)

6

SNU IDB Lab.





















(7)

SNU





(8)

8

SNU IDB Lab.

(9)

SNU

























(10)

10

SNU IDB Lab.





















(11)

SNU











(12)

12

SNU IDB Lab.













sequentialSearch



(13)

SNU











factorial

(14)

14

SNU IDB Lab.





(15)

SNU



















(16)

16

SNU IDB Lab.





(17)

SNU









(18)

18

SNU IDB Lab.



### Returns the position of the largest element in the array

 Operation count  the number of comparisons between elements of the array “a”

 When n <= 0, the for loop is not entered

 When n > 0, each iteration of the for loop makes one comparison





### Other operations are ignored (constant factor!)

 Initializing positionOfCurrentMax

 Incrementing for loop index i

### int positionOfCurrentMax = 0;

for(int i = 1; i <= n; i++)

if ( a[positionOfCurrentMax].compareTo(a[i]) < 0 ) positionOfCurrentMax = i;

return positionOfCurrentMax;

}

(19)

SNU

return value;

(20)

20

SNU IDB Lab.

// compute value

for

return

### •

n = coeff.length - 1

• The number of additions is n

• The number of multiplications is n

(21)

SNU















(22)

22

SNU IDB Lab.

### ("length of rank array cannot " + "be less than the no of objects");

for (int i = 0; i < a.length; i++) r[i] = 0;

for

for

### (int j = 0; j < i; j++)

if (a[j].compareTo(a[i]) <= 0) r[i]++;

else

### }

Total element comparisons is 1+ 2 + 3 + … + n-1 = (n-1) * n / 2

(23)

SNU

rank 함수는 리그전과 유사







### 

최종결과: r[i] = (i의 승수)



(24)

24

SNU IDB Lab.

(25)

SNU





(26)

26

SNU IDB Lab.

(27)

SNU















(28)

28

SNU IDB Lab.

(29)

SNU

(30)

30

SNU IDB Lab.

(31)

SNU











(32)

32

SNU IDB Lab.

1

=

n

i

(33)

SNU

### throw new IllegalArgumentException ("array not large enough");

// find proper place for x int i;

for (i = n - 1; i >= 0 && x.compareTo(a[i]) < 0; i--) a[i+1] = a[i];

a[i+1] = x; // insert x }

(34)

34

SNU IDB Lab.

(35)

SNU

(36)

36

SNU IDB Lab.

(37)

SNU

(38)

38

SNU IDB Lab.















(39)

SNU















(40)

40

SNU IDB Lab.

(41)

SNU























(42)

42

SNU IDB Lab.





(43)

SNU





















(44)

44

SNU IDB Lab.

(45)

SNU

(46)

46

SNU IDB Lab.

















(47)

SNU

(48)

48

SNU IDB Lab.

### Matrix Transpose Profiling (2)

Total

0 0 0 0 0 0

1 rows+1 rows+1

1 rows(rows+1)/2 rows(rows+1)/2 0 0 0

0 0 0

1 rows(rows-1)/2 rows(rows-1)/2 1 rows(rows-1)/2 rows(rows-1)/2 1 rows(rows-1)/2 rows(rows-1)/2 0 0 0

0 0 0

s/e Frequency Total steps public static void transpose(…)

{

for (int i = 0; i < rows; i++) for (int j = i+1; j < rows; j++) {

// swap a[i][j] and a[j][i]

int t = a[i][j];

a[i][j] = a[j][i];

a[j][i] = t;

} }

Statement

2

(49)

SNU

(50)

50

SNU IDB Lab.

### Prefix Sums profiling (2)

Total

0 0 0 0 0 0 0 0 0 n 1 n 0 0 0 0 0 0 1 n+1 n+1 2j+7 n n(n+6) 1 1 1 0 0 0

s/e Frequency Total steps public static int [] inef(int [] a)

{

// create an array for the prefix sums int [] b = new int [a.length];

// compute the prefix sums for (int j = 0; j < a.length; j++)

b[j] = MyMath.sum(a, j + 1);

return b;

}

Statement

2

(51)

SNU

(52)

52

SNU IDB Lab.

### Example 2.21

4 Total

0 0 0

0 0 0

1 1 1

1 1 1

1 1 1

1 1 1

0 0 0 s/e Frequency Total

steps public static int sequentialSearch(…)

{

int i;

for (i = 0; i < a.length&& !x.equals(a[i]); i++);

if (i == a.length) return -1;

else return i;

}

Statement

(53)

SNU

### Example 2.21

n+3 Total

0 0 0 0 0 0 1 1 1 1 n+1 n+1 1 1 1 1 0 0 0 0 0 s/e Frequency Total

steps public static int sequentialSearch(…)

{

int i;

for (i = 0; i < a.length&& !x.equals(a[i]); i++);

if (i == a.length) return -1;

else return i;

}

Statement

(54)

54

SNU IDB Lab.

### Example 2.21

j+4 Total

0 0 0 0 0 0 1 1 1 1 j+1 j+1 1 1 1 1 1 1 0 0 0 s/e Frequency Total

steps public static int sequentialSearch(…)

{

int i;

for (i = 0; i < a.length&& !x.equals(a[i]); i++);

if (i == a.length) return -1;

else return i;

}

Statement

(55)

SNU











(56)

56

SNU IDB Lab.

























Updating...

관련 주제 :