PDF Chapter 2: Program Performance (Big O Notation)

Chapter 2 ( Program performance ) 1- Factors that determine program performance a. Algorithms & data structures (major factor?) b. Hardware (speed of the processor) c. Compiler (different compilers for the same d. language give different performance) e. Programming lan...

Chapter 2 ( Program performance ) 1- Factors that determine program performance a. Algorithms & data structures (major factor?) b. Hardware (speed of the processor) c. Compiler (different compilers for the same d. language give different performance) e. Programming language f. Operating system 2- Efficiency of Algorithms a. The amount of memory used (space complexity) b. The amount to time it takes (time complexity) c. Note (Time and space both, depend on the input size) 3- Analysis of Algorithm a. Kinds of analyses : i. Worst-case: (usually) : maximum time of algorithm on any input of size n ii. Average-case: (sometimes) : expected time of algorithm over all inputs of size n. iii. Best-case: (NEVER!) : Cheat with a slow algorithm that works fast on some input. )1(  4- Basic operation: the operation that contributes the most towards the running time of the algorithm a. Basic operation : ‫ العمليات األساسية هي‬: ‫مالحظة هامة جدا‬ ) ‫العمليات الحسابية (جمع – طرح – ضرب – قسمة – باقي قسمة‬ -1 ) if ( ‫عمليات المقارنة‬ -2 ‫أو العملية التي عادة تتكرر في البرنامج (قد تكون عملية طباعة قد‬ -3 ) ‫تكون عملية قراءة‬ : ‫ويتم حساب إجمالي الزمن بالعادلة التالية‬ -4 ‫ عدد مرات التكرار‬x ‫ زمن تنفيذ العملية األساسية‬.a T(n) = Cop * C(n) ‫ هو إجمالي زمن التنفيذ‬T(n) ‫حيث‬ ‫ زمن التنفيذ للمرة الواحدة‬Cop ‫ عدد مرات التكرار‬C(n) Problem Input size measure Basic operation Searching for key in a list of n Number of list’s items, i.e. n Key comparison items ‫عدد عناصر القائمة‬ ‫عملية المقارنة‬ ‫البحث عن قيمة في قائمة من‬ ‫العناصر‬ Multiplication of two matrices Matrix dimensions or total Multiplication of two ‫ضرب مصفوفتين‬ number of elements numbers ‫إجمالي عدد عناصر المصفوفتين‬ ‫ضرب مصفوفتين‬ Checking primality of a given n’size = number of digits Division integer n (in binary ‫القسمة‬ ‫التحقق من األعداد األولية‬ representation) ‫عدد خانات العدد‬ Typical graph problem #vertices and/or edges Visiting a vertex or ‫الجراف‬ traversing an edge 5- Find The Basic Operation : static int method() { int[]array={5,10,9,8,12,14,9}; int k = 1; for (int i = 0; i < array.Length; i++) if (array[i] == k) return i; return -1; } )2(  1- static double method() { int[]array={5,10,9,8,12,14,9}; double ss = 0; for (int i = 0; i < array.Length; i++) ss = ss + array[i]; return ss; } int i ; for (i = 1; i= 99‬‬ ‫;‪b = a * a‬‬ ‫‪else‬‬ ‫;‪b = a + a‬‬ ‫(‪)5‬‬  4- FOR loops : a) ‫لوب مفرد عدد واحد لوب‬ for (i = 0; i < N; i++) { sequence of statements } b) ‫عدد اثنان لوب غي متداخل عملية جمع‬ for (i = 0; i < N; i++) { sequence of statements } for (j = 0; j < M; j++) { sequence of statements} c) ‫متداخلي نستد لوب عملية نضب‬ ‫ن‬ ‫عدد اثنان لوب‬ for (i = 0; i < N; i++) { for (j = 0; j < M; j++) { sequence of statements } } Examples : for (i = 0; i < N; i++) { for (j = i+1; j < N; j++) { sequence of statements } } )6( Examples for (i = 0; i < N; i++) { sequence of statements } for (j = 0; j < M; j++) { sequence of statements } Examples : for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { sequence of statements } } for (k = 0; k < N; k++) { sequence of statements } )7( Example for (i = 0; i < N; i++) { for (j = N; j > i; j--) { sequence of statements } } Note : ‫مالحظة هامة‬ ‫اذا اللوب به قسمة او ضرب او باقي قسمة يكون البيج او هو اللوج‬ for (int i = 1; i < n; i /= 2) Console.WriteLine("hassan eid"); Big (O)= log n )8( 3- ‫) فقط‬1( ‫الحظ البد من ان نأخذ اكبر عامل مؤثر في المعادلة مع مالحظة الثابت دائما قيمته‬ 4- Examples : Give the time complexity for the functions below using big-O notation: 5 a) F(n) = 4n2 + 3n – 2n + 10 2 b) F(n) = (n + 1)(5n3 + n – 2) c) for(i = 1; i