17208
DÙNG CHO SV NGÀNH :
-
-
-
-
TS
LT
TH/Xemina
BT
KT
5
4
0
1
0
0,5
3
2,5
1
1,5
1
1
11
6
3
2
0
quy
1
11
6
3
1
1
4.3.2. Quick sort
0,5
1,5 1,5 1
1 0,5
5.1.1.
1,5
1 1
1,5
1
0,5 1
1
0,5
iii
TS
LT
TH/Xemina
BT
KT
0,5
1
do giáo viên giao,
-
2003
- Algorithm 2
2
2
2
2
3
Algorithm Complexity 4
4
4
5
7
Data structure 9
9
9
Backtracking 9
9
10
11
11
13
13
13
13
13
14
15
15
17
19
21
O 65
66
1
.
10
Input.
tput.
2.
ng có hai cách biu din mt thut toán, cách th nht là mô t c thc hin
ca thut toán, cách th hai là s d gii thut.
2.1.
biu din thu i ta mô t c thc hin ca thut toán,
ngôn ng mô t thut toán có th là ngôn ng t nhiên hoc mt ngôn ng lai ghép
gia ngôn ng t nhiên vi mt ngôn ng l n gi mã lnh.
3
Ví d: mô t thu c s chung ln nht ca hai s nguyên.
Input: Hai s nguyên a, b.
.
Thut toán:
USCLN(a, b)=a.
m USCLN ca a-b và b, quay li
Nu a < b thì tìm USCLN ca a và b-a, quay li
) (flowchart)
(Algorithm Flowchart).
Bu
Trên thc t các thut toán hiu qu thì không d hit hiu qu
d dàng thc hin và hi c mt cách nhanh chóng. Và m u có v nghch lý là các
thut toán càng hiu qu thì càng khó hi t càng phc tp li càng hiu qu (không
ph nh giá và so sánh các thu ng da
phc tp v thi gian thc hin ca thut toán, g phc tp thut toán
(algorithm complexity). V bn ch phc tp thut toán là m ng (có th
không chính xác) s phép tính mà thut toán cn thc hin (t dàng suy ra thi gian
thc hin ca thu i vi mt b d lic N. N có th là s phn t
ca mng hp bài toán sp xp hoc tìm kim, hoc có th ln ca s trong
bài toán kim tra s nguyên t chng hn.
3.2. oán
minh ha vi phc tp thut toán ta xem xét ví d v thut toán sp xp
chn (selection sort) và sp xi ch trc ti
Cài t ca thut toán sp xp chn:
for(i=0;i<n;i++)
{
min_idx = i;
for(j=i+1;j<n;j++)
if(a[j]<a[min_idx])
min_idx = j;
if(min_idx!=i)
{
temp = a[i];
a[i] = a[min_idx];
a[min_idx] = temp;
}
5
}
O O
O
O(f(N)).
-
6
ta f(N) = N*(N-1)/2 = 0.5N
2
O(N
2
2
.
O(N
2
O(N
N*log(N) + 1000047N =
(N*log(N))
O (N
k
)
(N
2
)
O(N
2
O(N
5
)
(N*log(N))
est case).
7
k
f(N) =
(b
N
O
b
(N
2
2
7
N
2
.
.
(2N)
20
(N!)
11
O(Log(N))
10
-7
giây
O(N)
10
-6
giây
O(N*Log(N))
10
-5
giây
O(N
2
)
10
-4
giây
if (A[i]-A[j] == D)
return 1;
}
O(N
2
O(N)
9
O(N
2
O
4. Data structure
Niklaus Wirth, mt lp trình viên và nhà khoa h i phát minh ra ngôn
ng l ng nói mt câu nói ni ti c l
(Programs) = Cu trúc d liu (Data Structures) + Gii thut (Algorithms). Câu nói này nói
lên bn cht ca vic l t cu trúc d liu phù h biu din d liu ca
bài toán và t ng gii thut phù hp vi cu trúc d lichn. Ngày nay vi s
phát trin ca các k thut lp trình, câu nói ca Wirth không h i na
n phn ánh s gn kt và tm quan trng ca các cu trúc d liu và gii thut.
Cu trúc d li c s d biu din d liu còn các gii thuc s d thc
hin các thao tác trên các d liu ca bài toán nhm hoàn thành các ch
trình
.
[6, trang 57]:
N
a
.
N
a
N N/2 2
N/2 2
1 nÕu N = 0
a (a ) nÕu N ch½n
a*(a ) nÕu N lÎ
int power(int a, int n)
{
if(n==0)
return 1;
else{
int t = power(a, n/2);
if(n%2==0)
return t*t;
else
return a*t*t;
}
}
(Greedy)
7 8 9
n
*x
n
+ a
n-1
*x
n-1
+ +a
1
*x + a
0
f(x) = a
ca mi
+ Mt bn ghi (record) là mt tp hng
+ Mt file là mt tp hp các bn ghi
Sp xp (sorting) là mt quá trình x t các bn ghi ca mt file theo mt th t nào
c x c thc hin da trên mt hay nhi
c gi là khóa xp xp (key). Th t ca các bnh da trên các khóa
khác nhau và vic sp x c thc hi i vi mi khóa theo các th t khác nhau.
Chúng ta s tp trung vào các thut toán xp xp và gi s khóa ch gng duy nht.
Hu ht các thut toán xp xc gi là các thut toán xp xp so sánh: chúng s dng hai
i ch (swap) các phn t cn sp xp.
(internal sorting):
trong
Khi các b c ln vi i các bn ghi là rt t
gii ta có th s d p xp gián tip. Vic này có th c
thc hin theo nhiu cách khác nhau và môt trong nh o ra mt file
mi chng khóa cu, hoc con tr ti hoc là ch s ca các bn ghi ban
u. Chúng ta s sp xp trên file mi này vi các b c nh
cp vào các b u thông qua các con tr hoc ch s
ng thi vi các h qun tr d liu).
Shilst
Greg
8
234-45-5784
Sau khi sp x truy cp vào các bn ghi theo th t p xp chúng ta s
dng th t c cung cp bi ct index (ch sng hp này là 3, 2, 4, 1. (chúng
ta không nht thit phi các b u).
1.
Các thut toán sp xp có th c so sánh vi nhau da trên các yu t
+ Thi gian thc hin (run-time): s các thao tác thc hi ng là s các phép so
s i các bn ghi).
+ B nh s d ng b nh cn thi thc hin thut toán
ng b nh s d cha d liu cn sp xp.
+ Mt vài thut toán thuc lo n (hoc cn mt s c nh) thêm
b nh cho vic thc hin thut toán.
+ Các thu ng s dng thêm b nh t l thun theo hàm tuyn tính hoc
c file sp xp.
+ Tt nhiên là b nh s dng càng nh càng tt mc dù vii gia thi gian và
b nh cn thit có th là có li.
+ S nh (Stability):Mt thu c gi là nh n gi c
quan h th t ca các khóa b i th t ca các khóa bng nhau).
ng lo lng nhiu nht là v thi gian thc hin ca thut toán vì các thut
toán mà chúng ta bàn v ng s d c b nh
Ví d v sp xp nh: Chúng ta mun sp x trên ký t u ca các
b t qu sp xp ca các thut toán nh và không nh:
15
S
n mã sau minh ha cho thut toán:
void selection_sort(int a[], int n)
{
int i, j, vtmin;
17
for(i=0; i<n-1;i++)
{
vtmin = i; -1]
for(j=i+1;j<n;j++)
if(a[j] < a[vtmin])
vtmin = j;
swap(a[vtmin], a[i]);
}
}
Ví d:
Vi mi giá tr ca i thut toán thc hin (n i 1) phép so sánh và vì i chy t 0 cho ti
(n2), thut toán s cn (n-1) + (n--1)/2 tc là O(n
2
) phép so sánh.
i=i+1
j=j+1
S
S
i cha[i], a[j]
void exchange_sort(int a[], int n)
{
int i, j;
int tam;
for(i=0; i<n-1;i++)
19
for(j=i+1;j<n;j++)
if(a[j] < a[i])
{
tam = a[i];
a[i] = a[j];
a[j] = tam;
}
}
-
-
Copyright: Tài liệu đại học ©