Lecture 2. AlgorithmAnalysis

1. Ալգորիթմներ & տվյալների կառուցվածքներ

Ալգորիթմներ
&
տվյալների կառուցվածքներ
Algorithms
&
Data Structures

2. Ալգորիթմի վերլուծություն

• Criteria- չափանիշ
• Is it correct- ծշտություն
• Is it readable- ընթեռնելիություն
•…
• Performance Analysis (machine independent)համակարգչից անկախ
• space complexity - ծավալային բարդություն
• time complexity - ժամանակային բարդություն
• Performance Measurement (machine dependent)կախված է համակարգչից
2

3. Space Complexity Ծավալային բարդություն

S(P)=C+SP(I)
Fixed Space Requirements (C)- ֆիքսած մեծություն,
կախված չէ մուտքային/ելքային տվյալների
բնութագրերից
➢ instruction space – կոդի ծավալ
➢ space for simple variables, fixed-size structured variable,
constants
Variable Space Requirements (SP(I))- փոփոխական
մեծություն, կախված է I պարամետրից
➢ number, size, values of inputs and outputs
➢ recursive stack space, formal parameters, local variables,
return address
3

4.

Օրինակ 1. Sabc(I)=3*4(ֆորմալ պարամետրեր)+4(վերադարձվող
արժեք)+4(վերադարձի հասցե)=20բայթ
Օրինակ 2. Ssum(I)=Ssum(n)=2*4(ֆորմալ պարամետրեր)+2*4(լոկալ
փոփոխականներ)+4(վերադարձվող արժեք)+4(վերադարձի
հասցե)=24 բայթ
Recall: pass the address of the
first element of the array &
pass by value
4

5.

Օրինակ 3. Ռեկուրսիվ ֆունկցիա (գնահատված է մեկ ռեկուրսիվ
կանչի համար պահանջվող հիշողության ծավալը ստեկում)
Ընդհանուր ծավալը ստեկում՝
Ssum(I)=Ssum(n)=6n
5

6. Time Complexity ժամանակային բարդություն

T(P)=C+TP(I),
որտեղ C-ն կոմպիլացիայի ժամանակն է (compile time ) ,
TP(I) –ն կատարման ժամանակն է (run or execution time)
• Fixed time requirements- ֆիքսած ժամանակահատված
• Compile time (C), independent of instance characteristics
• Variable time requirements- փոփոխական
ժամանակահատված
• Run (execution) time TP
• TP(I) - կատարվող գործողությունների քանակ
6

7. Ժամանակային բարդության գնահատում

Գնահատում են ծրագրում կատարվող քայլերի
(հրամանների, գործողությունների) քանակը, որոնց
կատարման ժամանակը կախված չէ տվյալների
բնութագրերից
Օրինակ ՝
a + b + b * c + (a + b - c) / (a + b) + 4.0 (9 գործողություն/քայլ)
a + b + c (2 գործողություն/քայլ)
Methods to compute the step count
• Introduce variable count into programs - հաշվիչի
մեթոդ
• Tabular method – աղյուսակի մեթոդ
• որոշել յուրաքանչյուր քայլի կատարման ժամանակը և
կատարումների քանակը
• հաշվել գումարային ժամանակը ըստ բոլոր քայլերի
7

8. Օրինակ (հաշվիչի մեթոդ)

Թվերի հաջորդականության իտերատիվ գումարում
(count-ը հաշվում է հրամանների/գործողությունների
քանակը)
int count=0;
float sum(float list[ ], int n)
{
float tempsum = 0; count++; //=-ի համար
int i;
for (i = 0; i < n; i++) {
count++;
//for-ի համար
tempsum += list[i]; count++; // =-ի համար
}
count++;
//return-ի համար
return tempsum;
}
(2n + 2) գործողություն
8

9. Աղյուսակի մեթոդ. զանգվածում մեծագույն տարրի որոշում

Քայլի
կատարման Կատարումների Ժամանակային
ժամանակը քանակը
բարդությունը
վատագույն դեպքում
int find_max( int *array, int n ) {
}
int max = array[0];
for (int i = 1; i < n; ++i)
if ( array[i] > max )
max = array[i];
c1
c2
c3
c4
1
n-1
n-1
n-1
return max;
c5
1
c1+c2(n-1)+c3(n-1)+c4(n-1)
+ c5 <= Cmax*n = О(n)

10. Ալգորիթի կատարման ժամանակի կախվածությունը տվյալների կառուցվածքի ընտրությունից

Խնդիր. Որոշել զանգվածում իրարից տարբեր
տարրերի քանակը
Տվյալների կառուցվածքներ
• դինամիկ զանգված
• բազմություն
• հեշ-աղյուսակ
10

11. Ալգորիթմ 1 (ոչ արդյունավետ)

int main() {
int n;
std::cin >> n;
int* numbers = new int[n];
int distinctNumbersCount(const int* numbers,
int n) {
int count = 1;
for (int i = 1; i < n; i++) {
int j = 0;
for (; j < i; j++)
if (numbers[i] == numbers[j])
break;
for (int i = 0; i < n; i++)
numbers[i] = rand();
std::cout <<
distinctNumbersCount(numbers, n) ;
delete []numbers;
return 0;
}
if (i == j)
count++;
}
return count;
}
11

12. Ալգորիթմ 2 (արդյունավետ)

int main() {
int n;
std::cin >> n;
int* numbers = new int[n];
int distinctNumbersCountEffective(
const int* numbers, int n) {
return std::set<int>(numbers,
numbers+n).size();
}
for (int i = 0; i < n; i++)
numbers[i] = rand();
std::cout <<
distinctNumbersCountEffective
(numbers, n) ;
delete []numbers;
return 0;
}
12

13. Ալգորիթմ 3 (արդյունավետ)

int main() {
int n;
std::cin >> n;
int* numbers = new int[n];
int distinctNumbersCountEffective(
const int* numbers, int n) {
return std::unordered_set<int>(numbers,
numbers+n).size();
}
for (int i = 0; i < n; i++)
numbers[i] = rand();
std::cout <<
distinctNumbersCountEffective
(numbers, n) ;
delete []numbers;
return 0;
}
13

14. Ալգորիթմի աշխատանքի ժամանակի գնահատում

n
Ալգորիթմ 1
Ալգորիթմ 2
Ալգորիթմ 3
1.000
0.005 վրկ.
0.001 վրկ.
0.004 վրկ.
10.000
0.115 վրկ.
0.013 վրկ.
0.013 վրկ.
100.000
10 վրկ.
0.079 վրկ.
0.08 վրկ.
1.000.000
18 րոպ.52 վրկ.
1.2 վրկ.
1.2 վրկ.
10.000.000
> 1 ժամ
17 վրկ.
5 վրկ.
100.000.000
> 2 ժամ
3 րոպ. 53 վրկ.
57 վրկ.
14

15. Ալգորիթմների բարդության գնահատում

Ալգորիթմի ժամանակային հաշվողական
բարդությունը գնահատում են խնդրի չափի հիման
վրա (զանգվածում տարրերի քանակ, մատրիցի
տողերի և սյուների քանակ և այլն)
• լավագույն դեպքում
• միջինում
• վատագույն դեպքում
15

16. Ասիմպտոտիկ գնահատականներ

• Մեծ Օ
f(n) = O(g(n)), եթե գոյություն ունեն դրական c և n0
հաստանուններ, որ f(n) cg(n) բոլոր n-երի (n n0) համար:
• Omega -
f(n) = (g(n)), եթե գոյություն ունեն դրական c և n0
հաստանուններ, որ f(n) cg(n) բոլոր n-երի (n n0) համար:
• Theta-
f(n) = (g(n)) եթե գոյություն ունեն դրական c1, c2, և n0
հաստատուններ, որ c1g(n) f(n) c2g(n) բոլոր n-երի (n
n0)համար:
16

17. Օրինակներ

• f(n) = 3n+2
3n + 2 <= 4n, եթե n >= 2; հետևաբար 3n + 2 = (n)
3n + 2 >= 3n, եթե n >= 1; հետևաբար 3n + 2 = (n)
3n <= 3n + 2 <= 4n, եթե n >= 2; հետևաբար 3n + 2 = (n)
• f(n) = 10n2+4n+2
10n2+4n+2 <= 11n2, եթե n >= 4, հետևաբար 10n2+4n+2 = (n2)
10n2+4n+2 >= 10n2, եթե n >= 1, հետևաբար 10n2+4n+2 = (n2)
10n2 <= 10n2+4n+2 <= 11n2, եթե n >= 4, հետևաբար 10n2+4n+2 = (n2)
• f(n) =6*2n+n2
6*2n+n2 7*2n եթե n 4; հետևաբար 6*2n+n2 =O(2n)
17

18.  

18

19.  

19

20.  

20

21.  

21

22.  

22

23.  

23

24. Ֆունկցիաների աճը

24

25. Ֆունկցիաների աճը

25

26. Կատարման ժամանակի չափում

Անհրաժեշտ է որոշել, թե ինչքան ժամանակում է
կատարվում ծրագիրը տվյալ համակարգչի վրա:
26

27. Օրինակ

Թեստն իրականացվել է PC համակարգչի վրա. 80386 CPU,
80387 թվային կոպրոցեսոր, Borland’s Turbo C կոմպիլյատոր
(զանգվածի կարգավորում ընտրությամբ)
27