[Ansi C] Thuật toán nào tối ưu hơn?

[11520473]

Theo mọi người thì trong hai thuật toán dưới đây thì cái nào tối ưu hơn (Xét về độ phức tạp và thời gian thực hiện của chương trình)? Em thì nghĩ cái số 1 tối ưu hơn
Thuật toán 1:

void SapXepChenTructiep(int *a, int n)
{
	for (int i=1;i<n;i++)
	{
		int x=a[i];
		int pos=i-1;
		if (a[pos]>x)
		{
			while ((a[pos]>x) && (pos>=0))
			{
				a[pos+1]=a[pos];
				pos=pos-1;
			}
			a[pos+1]=x;
		}
	} 
}

Thuật toán 2:

void SapXepChenTructiep(int *a, int n)
{
	for (int i=1;i<n;i++)
	{
		int x=a[i];
		int pos=i-1;
		while ((a[pos]>x) && (pos>=0))
		{
			a[pos+1]=a[pos];
			pos=pos-1;
		}
		a[pos+1]=x;
	} 
}

Theo em thì:

Với cùng với 1 mảng 1 chiều có 5 số đã được sắp xếp không giảm hoàn toàn (TH tốt nhất) thì:
- Thuật toán 1: thực hiện 8 phép gán và 5 phép so sánh.
- Thuật toán 2: thực hiện 12 phép gán và 5 phép so sánh.

Còn với cùng với 1 mảng 1 chiều có 5 số đã được sắp xếp không tăng hoàn toàn (TH xấu nhất) thì:
- Thuật toán 1: thực hiện 32 phép gán và 12 phép so sánh.
- Thuật toán 2: thực hiện 32 phép gán và 8 phép so sánh.

Nhân đây cho em hỏi luôn là nếu trong câu lệnh sau: If (a>0 && b>0) .... thì khi a=0 thì không thực hiện các câu lệnh trong if luôn phải không (nghĩa là chỉ thực hiện 1 phép so sánh hay sao?).
Còn nếu khi (b=0 và a>0) thì phải thực hiện so sánh a>0 trước rồi mới so sánh b>0 hay không (thực hiện 2 phép so sánh) phải không?
Tóm lại có phải là thứ tự đặt câu lệnh trong thuật toán điều kiện nói riêng và trong các thuật toán nói chung là rất quan trọng phải không?
Mong mọi người giải đáp dùm.

[11520473]

sao không thấy ai vào trả lời dùm em hết nhỉ.

[09520019]

sao không thấy ai vào trả lời dùm em hết nhỉ. Hay mọi người không biết đánh giá thuật toán

Anh vừa gõ có bây nhiêu đây thôi, định chỉ em thêm mà F5 thì thấy dòng chữ màu đỏ thì anh định ko post nữa. Mà thôi lỡ gõ rồi thì copy cho em nhé. Anh vẫn còn đang chưa nói tiếp là cách nào để thấy cái Disassembly đó, em thông cảm tự google luôn vì anh bắt đầu ghét cái cách nói của em và sự thiếu kiên nhẫn. Còn đánh giá thuật toán thế nào hiệu quả em cũng tự google luôn đi vì đó là cách nhanh nhất. Post bài mới có vài tiếng mà nghĩ là có ngay câu trả lời sao ?

Chúc em may mắn lần sau

--------------------------------------------------------------------------------------------------

Theo em thì:

Với cùng với 1 mảng 1 chiều có 5 số đã được sắp xếp không giảm hoàn toàn (TH tốt nhất) thì:
- Thuật toán 1: thực hiện 8 phép gán và 5 phép so sánh.
- Thuật toán 2: thực hiện 12 phép gán và 5 phép so sánh.

Còn với cùng với 1 mảng 1 chiều có 5 số đã được sắp xếp không tăng hoàn toàn (TH xấu nhất) thì:
- Thuật toán 1: thực hiện 32 phép gán và 12 phép so sánh.
- Thuật toán 2: thực hiện 32 phép gán và 8 phép so sánh.

Theo anh thì em không thể đánh giá một thuật toán tốt hay xấu qua một hay 2 bộ test. Và càng sai lầm hơn khi đánh giá chúng chỉ qua yếu tố phép gán và phép so sánh.

Nhân đây cho em hỏi luôn là nếu trong câu lệnh sau: If (a>0 && b>0) .... thì khi a=0 thì không thực hiện các câu lệnh trong if luôn phải không (nghĩa là chỉ thực hiện 1 phép so sánh hay sao?).
Còn nếu khi (b=0 và a>0) thì phải thực hiện so sánh a>0 trước rồi mới so sánh b>0 hay không (thực hiện 2 phép so sánh) phải không?
Tóm lại có phải là thứ tự đặt câu lệnh trong thuật toán điều kiện nói riêng và trong các thuật toán nói chung là rất quan trọng phải không?
Mong mọi người giải đáp dùm.

Đoạn code sau sẽ giải đáp thắc mắc cho em:

	if (a > 0 && b > 0)
00D614C5  cmp         dword ptr [a],0  
00D614C9  jle         main+6Ch (0D614FCh)  
00D614CB  cmp         dword ptr [b],0  
00D614CF  jle         main+6Ch (0D614FCh)

đại loại là nó phân ra thành
if (a <= 0) nhảy tới X
if (b <= 0) nhảy tới X
Y: (đoạn lệnh khi a > 0 và b > 0);nhảy đến Z
X: (đoạn lệnh khi a > 0 và b > 0 là sai)
Z: tiếp theo....

[09520536]

Tính độ phức tạp của 2 thuật toán.

[ndttai.smileorcry]

lập trình C thi e po tay, pascal con biết sơ sơ

[09520536]

Cái này là thuật toán và cấu trúc dữ liêu chứ có liên quan gì đến ngôn ngữ đâu.

[08520195]

sao không thấy ai vào trả lời dùm em hết nhỉ. Hay mọi người không biết đánh giá thuật toán

Công nhận, muốn trả lời thiệt mà đọc cái hết cảm tình ...

[11520473]

Em xin lỗi mọi người, em thật là không nên làm như vậy vì dù sao mình cũng đang nhờ người khác mà. Nghe anh 09520019 Nguyễn Đăng Châu nói mà em cảm thấy thật có lỗi với anh. Em đâu có ngờ rằng khi em viết như vậy thì anh lại đang viết câu trả lời cho em. Em thành thật xin lỗi mọi người. Và em sẽ rút kinh nghiệm cho lần sau

[11520473]

EM vừa xóa câu nói đó mong mọi người thông cảm cho một phút nhất thời

[09520019]

Em xin lỗi mọi người, em thật là không nên làm như vậy vì dù sao mình cũng đang nhờ người khác mà. Nghe anh 09520019 Nguyễn Đăng Châu nói mà em cảm thấy thật có lỗi với anh. Em đâu có ngờ rằng khi em viết như vậy thì anh lại đang viết câu trả lời cho em. Em thành thật xin lỗi mọi người. Và em sẽ rút kinh nghiệm cho lần sau

Nói thế thì thêm 1 tí chứ a ko định làm tiếp đâu vì dạo này đang có vài việc riêng

Để trả lời cho câu số một của bạn, hồi chiều tôi đã code đoạn này.

#include <iostream>
#include <algorithm>
#include <time.h>
using namespace std;
void SapXepChenTructiep1(int *a, int n)
{
	for (int i=1;i<n;i++)
	{
		int x=a[i];
		int pos=i-1;
		if (a[pos]>x)
		{
			while ((a[pos]>x) && (pos>=0))
			{
				a[pos+1]=a[pos];
				pos=pos-1;
			}
			a[pos+1]=x;
		}
	} 
}
void SapXepChenTructiep2(int *a, int n)
{
	for (int i=1;i<n;i++)
	{
		int x=a[i];
		int pos=i-1;
		while ((a[pos]>x) && (pos>=0))
		{
			a[pos+1]=a[pos];
			pos=pos-1;
		}
		a[pos+1]=x;
	} 
}
void Randomizer(int *&a,int &n,int *&can1,int *&can2)
{
	int i;
	n = 100000 + rand() % 10000; //~~~~giam xuong neu qua cham, tang len neu qua nhanh (khoang 10s/test la OK)
	if (a != NULL) delete[] a;
	if (can1 != NULL) delete[] can1;
	if (can2 != NULL) delete[] can2;
	a = new int[n];
	can1 = new int[n];
	can2 = new int[n];
	for (i = 0;i < n;++i) a[i] = can1[i] = can2[i] = rand() % 2000000000 - 1000000000;
}
int Verifier(int *source,int n,int *c1,int *c2)
{
	int *veriarr;
	int res = 0,i;
	veriarr = new int[n];
	for (i = 0;i < n;++i) veriarr[i] = source[i];
	sort(veriarr,veriarr + n);
	for (i = 0;i < n;++i)
		if (veriarr[i] != c1[i])
		{
			res += 1;
			break;
		}
		for (i = 0;i < n;++i)
			if (veriarr[i] != c2[i])
			{
				res += 2;
				break;
			}
	delete[] veriarr;
	return res;
}
int main()
{
	srand(time(NULL));
	int *arr,*can1,*can2;
	int n = 0,i,res;
	arr = can1 = can2 = NULL;

	//for (i = 0;i < 1000;++i)
	while (true)
	{
		Randomizer(arr,n,can1,can2);
                //~~~~tick timer1
		SapXepChenTructiep1(can1,n);
                //~~~~tock timer1
                //~~~~tick timer2
		SapXepChenTructiep2(can2,n);
                //~~~~tock timer2
                //~~~~tick: bat dau bo dem thoi gian, giay thu 0, tock: dung bo dem thoi gian
                //tai day ta co them 2 bien totaltime1 & totaltime2, ta lam totaltime1 += timer1, totaltime2 += timer2
                //sau nhieu bo test, ta lay totaltime / n , so sanh ca 2
		res = Verifier(arr,n,can1,can2);
		if (res != 0)
		{
			cout << "VERIFIER ERROR " << res << endl; //1 = chentructiep1 sai, 2 = chentructiep2 sai, 3 = ca 2 deu sai
                        //~~~~chi su dung khi co "VERIFIER ERROR" xay ra
                        //fstream fout;
                        //fout.open("failcase.txt",fstream::out);
                        //fout << n << endl;
                        //for (int idebug = 0;idebug < n;++idebug) fout << arr[i] << ' ';fout << endl;
                        //fout.close();
			system("pause");
		}
	}
	system("pause");
	return 0;
}

Trước hết thì tôi xin trả lời "miệng" là tôi thích cách code số 2 hơn. Đơn giản là tôi thích nó ngắn 1 tí. Còn về độ phức tạp thì cả 2 đều là O(n^2) nên việc bạn thêm 1 cái if đấy tôi nghĩ là chẳng nhanh hơn bao nhiêu đâu, cùng lắm là nhanh hơn vài% thời gian. Trong khi đó nếu code phức tạp thì người code sẽ thấy lùng bùng con mắt, dễ bug. Nên tôi chuyển từ style code tối ưu => style code ngắn cũn cỡn + giải thuật tốt

Còn để chứng minh thì tôi tiếp cận theo phương pháp chạy nhiều bộ test, cộng tất cả thời gian lại, sau đó chia ra lấy giá trị trung bình. Nhờ cách này mà Quicksort được đánh giá độ phức tạp trong TH xấu nhất là O(n^2), nhưng khi chạy trên bộ test random thì thấy chỉ đạt O(n log n), còn O(n^2) là ai đó xui quá, cỡ (1/n!) sẽ bị dính độ phức tạp O(n^2). Với lại nếu chỉ dùng phép gán và phép so sánh thì tôi không nghĩ là có thể đánh giá hết được, vì khi chuyển sang mã máy, mỗi dòng lệnh như phép gán sẽ tạo ra 2 3 dòng lệnh mới, mà mỗi lệnh thì nhanh chậm khác nhau, đó là chưa kể cùng một lệnh truy xuất, lỡ cái địa chỉ đó nằm trên Cache CPU, RAM, pagefile sẽ cho tốc độ khác nhau. Nhưng dù gì thì bạn ở mức độ mới tập tành lập trình nên tôi nghĩ không nên phức tạp hóa đến mức đó. Nên tôi thích kiểu code ngắn mà được việc + đáp ứng yêu cầu hơn là code dài , vượt yêu cầu mà lại khó hiểu + dễ bug.

chỉ mới code đến đấy (chạy được), nhưng chưa code hết toàn bộ. Bạn search trong đoạn code trên những chỗ có ~~~~ là những chỗ tôi đánh dấu là chưa code.
reference bạn có thể sử dụng

http://www.cplusplus.com/reference/clibrary/ctime/

Để hoàn thành đoạn code trên

PS: À quên, để xem assembly thì trong Visual Studio, khi đang debug (F5 có breakpoint, hoặc F10/F11) bấm Alt + 8 hoặc Debug => Windows => Disassembly để thấy về mã ASM. Mã ASM cũng không có gì khó hiểu lắm, cứ nhớ nó theo quy tắc
+Viết tắt
+DEStination,SouRCe

ví dụ 1: JLE = Jump if Less than or Equal (nhảy nếu bé hơn hoặc bằng)
Vậy JGE là gì ? gợi ý: G = Greater.
ví dụ 2: ADD EAX,3
ADD = cộng, EAX = đừng quan tâm lắm, nhưng cứ cho nó là biến
vậy ADD EAX,3 có nghĩa là: EAX = EAX + 3; (Câu lệnh không tương đương nhưng ý nghĩa là EAX cộng thêm 3 đơn vị)

dùng kèm với (Breakpoint + F5), F10, F11 trong debug mode thì bạn có thể hiểu được khá nhiều về cách hoạt động.

PS2: Đoạn code trên hiện đang lặp vô tận, dùng Ctrl + C để thoát, tại vì trước khi tôi test thời gian thì tôi phải test xem nó chạy đúng không đã.

[11520473]

Em cảm ơn anh. Mặc dù em đọc chưa hiểu hết những gì anh viết nhưng em cảm ơn anh đã quan tâm đến câu hỏi của em đặt ra, cảm ơn anh đã bỏ thời gian ra để viết bài này

[07520004]

Thuật toán 1:

void SapXepChenTructiep(int *a, int n)
{
	for (int i=1;i<n;i++)
	{
		int x=a[i];
		int pos=i-1;
		if ([B]a[pos]>x[/B])
		{
			while ([B](a[pos]>x)[/B] && (pos>=0))
			{
				a[pos+1]=a[pos];
				pos=pos-1;
			}
			a[pos+1]=x;
		}
	} 
}

Thứ nhất:
Khi không tốn cái if chẳng để làm gì, chỉ tổ cho nó rối sự đời. Nếu điều kiện được in đậm sai thì vòng while sẽ không chạy, có hay không có cái if đó cũng thế.
Thử chạy đoạn code

 int a = 5; cout << (a != 5 && a/0); 

Thử xem nó có báo division by zero hay không là em sẽ hiểu cách compiler tính giá trị của logical expression.
Cái này là biểu hiện của học tin đại cương không kỹ lưỡng nè, không chịu viết code để thử nghiệm mà chỉ chủ quan duy ý chí.


Thứ hai:
Hai cái code này là cùng một thuật toán, cài đặt khác nhau, nên nó chỉ có 1 độ phức tạp duy nhất, chả có gì để so sánh cả. Câu hỏi đáng ra phải là "cách cài đặt nào" chạy nhanh hơn. Không phải cứ sửa dăm ba chỗ trong phần cài đặt là tự nhiên phát kiến ra được một thuật toán mới.

[11520338]

Nói thế thì thêm 1 tí chứ a ko định làm tiếp đâu vì dạo này đang có vài việc riêng

Để trả lời cho câu số một của bạn, hồi chiều tôi đã code đoạn này.

#include <iostream>
#include <algorithm>
#include <time.h>
using namespace std;
void SapXepChenTructiep1(int *a, int n)
{
	for (int i=1;i<n;i++)
	{
		int x=a[i];
		int pos=i-1;
		if (a[pos]>x)
		{
			while ((a[pos]>x) && (pos>=0))
			{
				a[pos+1]=a[pos];
				pos=pos-1;
			}
			a[pos+1]=x;
		}
	} 
}
void SapXepChenTructiep2(int *a, int n)
{
	for (int i=1;i<n;i++)
	{
		int x=a[i];
		int pos=i-1;
		while ((a[pos]>x) && (pos>=0))
		{
			a[pos+1]=a[pos];
			pos=pos-1;
		}
		a[pos+1]=x;
	} 
}
void Randomizer(int *&a,int &n,int *&can1,int *&can2)
{
	int i;
	n = 100000 + rand() % 10000; //~~~~giam xuong neu qua cham, tang len neu qua nhanh (khoang 10s/test la OK)
	if (a != NULL) delete[] a;
	if (can1 != NULL) delete[] can1;
	if (can2 != NULL) delete[] can2;
	a = new int[n];
	can1 = new int[n];
	can2 = new int[n];
	for (i = 0;i < n;++i) a[i] = can1[i] = can2[i] = rand() % 2000000000 - 1000000000;
}
int Verifier(int *source,int n,int *c1,int *c2)
{
	int *veriarr;
	int res = 0,i;
	veriarr = new int[n];
	for (i = 0;i < n;++i) veriarr[i] = source[i];
	sort(veriarr,veriarr + n);
	for (i = 0;i < n;++i)
		if (veriarr[i] != c1[i])
		{
			res += 1;
			break;
		}
		for (i = 0;i < n;++i)
			if (veriarr[i] != c2[i])
			{
				res += 2;
				break;
			}
	delete[] veriarr;
	return res;
}
int main()
{
	srand(time(NULL));
	int *arr,*can1,*can2;
	int n = 0,i,res;
	arr = can1 = can2 = NULL;

	//for (i = 0;i < 1000;++i)
	while (true)
	{
		Randomizer(arr,n,can1,can2);
                //~~~~tick timer1
		SapXepChenTructiep1(can1,n);
                //~~~~tock timer1
                //~~~~tick timer2
		SapXepChenTructiep2(can2,n);
                //~~~~tock timer2
                //~~~~tick: bat dau bo dem thoi gian, giay thu 0, tock: dung bo dem thoi gian
                //tai day ta co them 2 bien totaltime1 & totaltime2, ta lam totaltime1 += timer1, totaltime2 += timer2
                //sau nhieu bo test, ta lay totaltime / n , so sanh ca 2
		res = Verifier(arr,n,can1,can2);
		if (res != 0)
		{
			cout << "VERIFIER ERROR " << res << endl; //1 = chentructiep1 sai, 2 = chentructiep2 sai, 3 = ca 2 deu sai
                        //~~~~chi su dung khi co "VERIFIER ERROR" xay ra
                        //fstream fout;
                        //fout.open("failcase.txt",fstream::out);
                        //fout << n << endl;
                        //for (int idebug = 0;idebug < n;++idebug) fout << arr[i] << ' ';fout << endl;
                        //fout.close();
			system("pause");
		}
	}
	system("pause");
	return 0;
}

Trước hết thì tôi xin trả lời "miệng" là tôi thích cách code số 2 hơn. Đơn giản là tôi thích nó ngắn 1 tí. Còn về độ phức tạp thì cả 2 đều là O(n^2) nên việc bạn thêm 1 cái if đấy tôi nghĩ là chẳng nhanh hơn bao nhiêu đâu, cùng lắm là nhanh hơn vài% thời gian. Trong khi đó nếu code phức tạp thì người code sẽ thấy lùng bùng con mắt, dễ bug. Nên tôi chuyển từ style code tối ưu => style code ngắn cũn cỡn + giải thuật tốt

Còn để chứng minh thì tôi tiếp cận theo phương pháp chạy nhiều bộ test, cộng tất cả thời gian lại, sau đó chia ra lấy giá trị trung bình. Nhờ cách này mà Quicksort được đánh giá độ phức tạp trong TH xấu nhất là O(n^2), nhưng khi chạy trên bộ test random thì thấy chỉ đạt O(n log n), còn O(n^2) là ai đó xui quá, cỡ (1/n!) sẽ bị dính độ phức tạp O(n^2). Với lại nếu chỉ dùng phép gán và phép so sánh thì tôi không nghĩ là có thể đánh giá hết được, vì khi chuyển sang mã máy, mỗi dòng lệnh như phép gán sẽ tạo ra 2 3 dòng lệnh mới, mà mỗi lệnh thì nhanh chậm khác nhau, đó là chưa kể cùng một lệnh truy xuất, lỡ cái địa chỉ đó nằm trên Cache CPU, RAM, pagefile sẽ cho tốc độ khác nhau. Nhưng dù gì thì bạn ở mức độ mới tập tành lập trình nên tôi nghĩ không nên phức tạp hóa đến mức đó. Nên tôi thích kiểu code ngắn mà được việc + đáp ứng yêu cầu hơn là code dài , vượt yêu cầu mà lại khó hiểu + dễ bug.

chỉ mới code đến đấy (chạy được), nhưng chưa code hết toàn bộ. Bạn search trong đoạn code trên những chỗ có ~~~~ là những chỗ tôi đánh dấu là chưa code.
reference bạn có thể sử dụng

http://www.cplusplus.com/reference/clibrary/ctime/

Để hoàn thành đoạn code trên

PS: À quên, để xem assembly thì trong Visual Studio, khi đang debug (F5 có breakpoint, hoặc F10/F11) bấm Alt + 8 hoặc Debug => Windows => Disassembly để thấy về mã ASM. Mã ASM cũng không có gì khó hiểu lắm, cứ nhớ nó theo quy tắc
+Viết tắt
+DEStination,SouRCe

ví dụ 1: JLE = Jump if Less than or Equal (nhảy nếu bé hơn hoặc bằng)
Vậy JGE là gì ? gợi ý: G = Greater.
ví dụ 2: ADD EAX,3
ADD = cộng, EAX = đừng quan tâm lắm, nhưng cứ cho nó là biến
vậy ADD EAX,3 có nghĩa là: EAX = EAX + 3; (Câu lệnh không tương đương nhưng ý nghĩa là EAX cộng thêm 3 đơn vị)

dùng kèm với (Breakpoint + F5), F10, F11 trong debug mode thì bạn có thể hiểu được khá nhiều về cách hoạt động.

PS2: Đoạn code trên hiện đang lặp vô tận, dùng Ctrl + C để thoát, tại vì trước khi tôi test thời gian thì tôi phải test xem nó chạy đúng không đã.

Em đọc mà hết buồn ngũ..thank anh. Em dây học bài liền!!!

[11520473]

Em cảm ơn anh nhiều nha. Giờ thì em đã hiểu thật sự cách xử lí của C

Thử chạy đoạn code
PHP Code:
int a = 5; cout << (a != 5 && a/0);
Thử xem nó có báo division by zero hay không là em sẽ hiểu cách compiler tính giá trị của logical expression.
Cái này là biểu hiện của học tin đại cương không kỹ lưỡng nè, không chịu viết code để thử nghiệm mà chỉ chủ quan duy ý chí.

[11520338]

mình thi chưa hiểu

Em cảm ơn anh nhiều nha. Giờ thì em đã hiểu thật sự cách xử lí của C