CH1 2018 8 27 ( ) 2018 8 27 1 / 35
( ) 2018 8 27 2 / 35
https://giteecom/bzu-ds/ds-cpp https://giteecom/bzu-ds/cpp-dev-tools C++ https://perusallcom Course code:?????? ( ) 2018 8 27 2 / 35
1) 2) 3) 4) ( ) 2018 8 27 3 / 35
1-1 1-2 1-3 ( ) 2018 8 27 4 / 35
( ) 2018 8 27 5 / 35
( ) 2018 8 27 6 / 35
1) 2) ( ) 2018 8 27 7 / 35
3) 4) ( ) 2018 8 27 8 / 35
(D,S) D S D 1-4 1-5 ( ) 2018 8 27 9 / 35
bit 0/1 ( ) 2018 8 27 10 / 35
( ) 2018 8 27 11 / 35
( ) 2018 8 27 12 / 35
ADT 1 2 ( ) ( ) ( ) ( ) 2018 8 27 13 / 35
ADT (D,S,P) D S D P D 1-6 ADT ( ) 2018 8 27 14 / 35
( ) 2018 8 27 15 / 35
C/C++ C TRUE/FALSE, OK/ERROR Status C++, cin, cout E&, const E& template new, delete throw, try-catch 1-7 ( ) 2018 8 27 16 / 35
( ) 2018 8 27 17 / 35
( ) 2018 8 27 18 / 35
a b c d ( ) 2018 8 27 19 / 35
( ) 2018 8 27 20 / 35
n f(n) T (n) = O(f(n)) ( ) 2018 8 27 21 / 35
f(n) = 3n 2 + 5n + 7 O O(3n 2 + 5n + 7) = O(n 2 ) 1 O(3n) = O(n) 2 O(3n 2 + 5n) = O(n 2 ) ( ) 2018 8 27 22 / 35
+ 1 2 3 ( ) 2018 8 27 23 / 35
O(1) O(log n) O(n) O(polynomial(n)) O(1), O(n), O(n 2 ), O(n 3 ) O(2 n ), O(3 n ) f(n) 4,000 3,000 2,000 1,000 200 log 2 n 100n 5n 2 n 3 2 2 n 0 0 5 10 15 20 25 30 n ( ) 2018 8 27 24 / 35
( ) 2018 8 27 25 / 35
a[n] x -1 int find(e a[], int n, E x) { for(i=0; i<n; i++) { if(a[i]==x) return i; return -1; // not found ( ) 2018 8 27 26 / 35
a[n] x -1 int find(e a[], int n, E x) { for(i=0; i<n; i++) { if(a[i]==x) return i; return -1; // not found n ( ) 2018 8 27 26 / 35
a[n] x -1 int find(e a[], int n, E x) { for(i=0; i<n; i++) { if(a[i]==x) return i; return -1; // not found n O(n) ( ) 2018 8 27 26 / 35
a[n] x int binary_search(e a[], int n, const E& x) { int low, mid, high; low = 0; high = n-1; while(low <= high) { mid = (low + high) / 2; if(a[mid] < x) low = mid + 1; else if(a[mid] > x) high = mid - 1; else return mid; return -1; // not found ( ) 2018 8 27 27 / 35
a[n] x log 2 n + 1 ( ) 2018 8 27 28 / 35
a[n] x log 2 n + 1 O(log n) ( ) 2018 8 27 28 / 35
a[n] E min(e a[], int n) { E tmp = a[0]; for(int i=1; i<n; i++) if(a[i] < tmp) tmp = a[i]; return tmp; ( ) 2018 8 27 29 / 35
a[n] E min(e a[], int n) { E tmp = a[0]; for(int i=1; i<n; i++) if(a[i] < tmp) tmp = a[i]; return tmp; n 1 ( ) 2018 8 27 29 / 35
a[n] E min(e a[], int n) { E tmp = a[0]; for(int i=1; i<n; i++) if(a[i] < tmp) tmp = a[i]; return tmp; n 1 O(n) ( ) 2018 8 27 29 / 35
( ) 2018 8 27 30 / 35
3n 2 1 ( ) 2018 8 27 30 / 35
x n n double power(double x, int n) { if(n<0) throw std::invalid_argument("n<0"); if(n==0) return 1; else if(n&1) // odd or not return power(x*x, n/2)*x; else return power(x*x, n/2); ( ) 2018 8 27 31 / 35
x n n double power(double x, int n) { if(n<0) throw std::invalid_argument("n<0"); if(n==0) return 1; else if(n&1) // odd or not return power(x*x, n/2)*x; else return power(x*x, n/2); log 2 n ( ) 2018 8 27 31 / 35
x n n double power(double x, int n) { if(n<0) throw std::invalid_argument("n<0"); if(n==0) return 1; else if(n&1) // odd or not return power(x*x, n/2)*x; else return power(x*x, n/2); log 2 n O(log n) ( ) 2018 8 27 31 / 35
0 n = 0 f(n) = 1 n = 1 f(n 1) + f(n 2) n > 1 long long fib(int n) { if(n<=1) return n; else return fib(n-1) + fib(n-2); ( ) 2018 8 27 32 / 35
0 n = 0 f(n) = 1 n = 1 f(n 1) + f(n 2) n > 1 long long fib(int n) { if(n<=1) return n; else return fib(n-1) + fib(n-2); O(2 n ) ( ) 2018 8 27 32 / 35
0 n = 0 f(n) = 1 n = 1 f(n 1) + f(n 2) n > 1 long long fib(int n) { if(n<=1) return n; else return fib(n-1) + fib(n-2); O(2 n ) O(n) ( ) 2018 8 27 32 / 35
void bubble_sort(e a[], int n) { for(int i=0; i<n-1; i++) { bool change = false; for(int j=0; j<n-i-1; j++) { if(a[j] > a[j+1]) { swap(a[j], a[j+1]); change = true; if(!change) break; O(n 2 ) ( ) 2018 8 27 33 / 35
void bubble_sort(e a[], int n) { for(int i=0; i<n-1; i++) { bool change = false; for(int j=0; j<n-i-1; j++) { if(a[j] > a[j+1]) { swap(a[j], a[j+1]); change = true; if(!change) break; O(n 2 ) O(n) ( ) 2018 8 27 33 / 35
O ( ) 2018 8 27 34 / 35
( ) 2018 8 27 35 / 35