Đo trực tiếp thời gian chạy của thuật toán

Đo thời gian chạy là một trong những cách để đánh giá hiệu quả của một thuật toán. Công việc nghe có vẻ khó khăn nhưng thực tế, với các hàm, kiểu dữ liệu được định nghĩa trong thư viện time.h của C (trong C++ có thể dùng cả time.h hoặc ctime), ta có thể đo thời gian chạy của một đoạn chương trình bất kỳ một cách dễ dàng.

Trước hết cần tìm hiểu những thành phần cần thiết:

• clock_t : là một kiểu dữ liệu được dùng để đếm clock tick. Clock tick là đơn vị thời gian đặc biệt có mối quan hệ với hằng số CLOCKS_PER_SEC (thông thường là 1/1000 giây).
• clock() : là một hàm trả về thời gian xử lý của chương trình. Kiểu dữ liệu trả về là clock_t
• CLOCKS_PER_SEC: là một hằng số macro đại diện cho số clock tick mỗi giây (thường là 1000).

Vậy để đo thời gian chạy của một đoạn chương trình, ta dùng các biến clock_t ghi lại thời gian thực hiện rồi chia cho hằng số CLOCKS_PER_SEC để ra được số giây thực hiện.

Có thể xem ví dụ mẫu sau:

int main()
{
   clock_t begin = clock(); //ghi lại thời gian đầu

   //Đoạn chương trình cần đo

   clock_t end = clock(); //ghi lại thời gian lúc sau
   cout<<"Time run: "<<(float)(end-begin)/CLOCKS_PER_SEC<<" s"<<endl;
   return 0;
}

Thuật toán sắp xếp: Selection Sort (chọn trực tiếp)

Selection Sort là một thuật toán sắp xếp tương đối dễ hiểu. Ý tưởng chính vẫn là đổi chỗ những cặp nghịch thế, tuy nhiên cái hay là ở chỗ Selection Sort tìm vị trí chứa phần tử nhỏ nhất để đổi chỗ với phần tử đang xét chứ không đổi tất cả các cặp nghịch thế như Bubble Sort hay Interchange Sort.

Ý tưởng
Xét phần tử đầu tiên của dãy. Tìm phần tử nhỏ nhất trong các phần tử còn lại. Hoán đổi phần tử đầu tiên với phần tử nhỏ nhất này, ta được phần tử đầu tiên có vị trí đúng. Bỏ qua phần tử vừa được xét, tiếp tục xét đến phần tử kế tiếp và thực hiện đến hết dãy.

Cài đặt trong C++

int min, i, j; //min là chỉ số phần tử nhỏ nhất
for(i = 0; i < n-1; i++)
{
   min = i;
   for(j = i+1; j < n; j++)
      if(a[j] < a[min])
         min = j; //tìm min trong các phần tử còn lại
   if(min != i)
     swap(a[i], a[min]); //đổi chỗ nếu tìm thấy min
}

Minh họa
Nguồn: Wikipedia

Đánh giá
Về số phép so sánh, ở lượt xét thứ i luôn có (n-i) phép so sánh để tìm min và không phụ thuộc tình trạng ban đầu của dãy nên số phép so sánh ước lượng là: (n-1) + (n-2) + ... + 1 = n(n - 1)/2.

Số lần hoán vị ở trường hợp tốt nhất là 0.
Trường hợp xấu nhất là: 3n(n-1)/2.

Độ phức tạp là: O(n²)

Thuật toán sắp xếp: Bubble Sort (sắp xếp nổi bọt)

Bubble Sort là một thuật toán sắp xếp kiểu so sánh rất đơn giản và dễ hiểu. Ý tưởng chính của thuật toán này là bắt cặp tất cả các phần tử trong dãy cần sắp xếp và đổi chỗ hai phần tử trong cặp nếu chúng nghịch thế (không thỏa điều kiện thứ tự).

Ý tưởng
Đối với Bubble Sort, ta chọn cặp bằng cách xét hai phần tử kế cận nhau.
Có 2 dạng sắp xếp của Bubble Sort

Dạng 1: Sắp từ đầu đến cuối
Xuất phát từ đầu dãy, ta so sánh và đổi chỗ các cặp nghịch thế đến cuối dãy để đưa phần tử lớn nhất về cuối dãy. Khi đó chỉ việc xét các phần tử còn lại trong dãy và lặp lại các bước để sắp xếp.

Dạng 2: Sắp từ cuối lên đầu
Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử nghịch thế để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.

Cài đặt theo ngôn ngữ C++
Dạng 1: Sắp từ đầu đến cuối

int i, j;
for (i = n-1 ; i > 0; i--)
   for (j = 0; j < i; j++)
      if (a[j] > a[j+1]) //nghịch thế
         swap(a[j],a[j-1]); //đổi chổ

Dạng 2: Sắp từ cuối lên đầu

int i, j;
for (i = 0; i < n-1; i++)
   for (j = n-1; j > i; j--)
      if (a[j-1] > a[j]) //nghịch thế
         swap(a[j],a[j-1]); //đổi chỗ

Minh họa
Dưới đây là minh hoạ cho thuật toán Bubble Sort theo dạng 1 (nguồn: Wikipedia)

Đánh giá
Số phép so sánh không phụ thuộc vào tình trạng ban đầu của dãy. Có thể ước lượng số phép so sánh bằng: (n-1) + (n-2) + ... + 1 = n(n - 1)/2.

Số phép hoán vị (3 phép gán) phụ thuộc tình trạng ban đầu. Trong trường hợp tốt nhất, tức dãy đã được sắp xếp hoàn toàn thì không cần phải hoán vị, nên số phép hoán vị là: 0.
Trường hợp xấu nhất, tức dãy có thứ tự ngược với yêu cầu. Mỗi lần so sánh ta lại phải hoán vị nên số phép hoán vị là: n(n - 1)/2.

Độ phức tạp của thuật toán này là: O(n²)

Thuật toán sắp xếp: Interchange Sort (đổi chỗ trực tiếp)

Để sắp xếp một dãy, có nhiều cách làm khác nhau. Trong bài viết này mình sẽ nói về Interchange Sort, hay còn gọi là thuật toán sắp xếp đổi chỗ trực tiếp.

Ý tưởng
Ý tưởng của thuật toán này là bắt cặp tất cả các phần tử trong dãy cần sắp xếp và đổi chỗ hai phần tử trong cặp nếu chúng nghịch thế (không thỏa điều kiện thứ tự).

Để bắt cặp tất cả các phần tử trong dãy, ta dùng 2 vòng lặp. Vòng lặp ngoài sẽ chạy từ đầu dãy đến phần tử kế cuối. Vòng lặp trong sẽ chạy từ phần tử tiếp theo của vị trí đang xét ở vòng lặp ngoài. Mỗi lần xét ta sẽ so sánh 2 phần tử trong cặp. Nếu chúng nghịch thế thì sẽ hoán đổi vị trí của chúng.

Ta thấy sau mỗi lần duyệt ở vòng lặp ngoài ta sẽ được phần tử đầu tiên đứng đúng thứ tự yêu cầu. Cứ thực hiện đến hết dãy ta sẽ được một dãy đã sắp xếp

Cài đặt
Mã dưới đây được cài đặt theo ngôn ngữ C/C++ với yêu cầu sắp xếp dãy tăng dần

void InterchangeSort(int *a, int n)
{
   for (int i = 0; i < n-1; i++)
      for (int j = i+1; j < n; j++)
         if (a[i] > a[j])
         {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
         }
}

Đánh giá
Số phép so sánh của thuật toán này không đổi, không phụ thuộc tình trạng ban đầu của dãy. Phần tử thứ i được so sánh với n-i phần tử còn lại nên có thể ước lượng số phép so sánh bằng: (n-1) + (n-2) + ... + 1 = n(n - 1)/2.

Tuy nhiên số phép hoán vị (3 phép gán) lại phụ thuộc tình trạng ban đầu. Trong trường hợp tốt nhất, tức dãy đã được sắp xếp hoàn toàn thì không cần phải hoán vị, nên số phép hoán vị là: 0.
Trường hợp xấu nhất, tức dãy có thứ tự ngược với yêu cầu. Mỗi lần so sánh ta lại phải hoán vị nên số phép hoán vị là: n(n - 1)/2.

Độ phức tạp của thuật toán này là: O(n²)

Hàm xóa một hàng và một cột bất kỳ trong ma trận

Có thể viết hàm xóa một hàng riêng và xóa một cột riêng và gọi chúng để xóa một hàng và một cột trong ma trận. Tuy nhiên, như vậy sẽ duyệt ma trận đến 2 lần. Để tối ưu hóa, ta có thể thực hiện xóa cùng lúc 1 hàng và một cột bằng cách sau đây.

Để dễ hiểu có thể xem hình minh họa:

Giả sử gọi cột cần xóa là iColumn và hàng cần xóa là iRow thì cả 2 sẽ tạo nên 4 vùng. Chỉ có vùng phía trên bên trái giữ nguyên còn các vùng khác di chuyển theo hướng như trên hình. Vùng phía trên bên phải sẽ dịch sang trái 1 cột, vùng phía dưới bên trái sẽ dịch lên 1 hàng và vùng phía dưới bên phải sẽ dịch xéo lên phía trái.

Như vậy ta sẽ minh họa cách làm bằng C/C++ như sau:

void DeleteRowColumn(int a[][20], 
                        int &m, int &n, int iRow, int iColumn)
{
   for(int i=0;i<m;i++)
      for(int j=0;j<n;j++)
      {
         if(i < iRow && j >= iColumn) //Vùng phía trên bên phải
            a[i][j]=a[i][j+1];
         else if(i >= iRow && j < iColumn) //Vùng phía dưới bên trái
            a[i][j]=a[i+1][j];
         else if(i >= iRow && j >= iColumn) //Vùng phía dưới bên phải
            a[i][j]=a[i+1][j+1];
      }
   m--;
   n--;
}

Các vấn đề cơ bản về số nguyên tố trong lập trình

Số nguyên tố là số chỉ có 2 ước, đó là 1 và chính nó, tức là nó chỉ chia hết cho số 1 và chính nó. Số 1 và 0 không được coi là số nguyên tố. Các bài toán cơ bản về số nguyên tố gồm kiểm tra một số nguyên n có phải là số nguyên tố và tìm các số nguyên tố nhỏ hơn hoặc bằng một số nguyên cho trước.

Kiểm tra một số nguyên có là số nguyên tố
Ý tưởng: Kiểm tra xem số n có chia hết cho từng số nhỏ hơn nó hay không. Nếu có thì không là số nguyên tố, nếu tất cả đều không có thì là số nguyên tố.

Cài đặt bằng C: Nếu số n là 1 hoặc 0 thì không là số nguyên tố. Dùng một vòng for chạy từ 2 đến n-1 để kiểm tra xem n có chia hết cho bất kỳ số nào trong đó không, nếu có thỉ không là số nguyên tố, nếu tất cả đều không thì là số nguyên tố. Trong một hàm nếu gặp lệnh return, hàm sẽ trả về giá trị và kết thúc hàm nên có thể viết gọn như sau:

int IsPrime(int n)
{
   if (n < 2) return 0;
   for(int i = 2; i < n; i++)
      if(n%i==0) return 0; 
   return 1; 
}

Tuy nhiên có thể nhận thấy việc kiểm tra đến n-1 là không cần thiết. Vì nếu n có các ước thì các ước của nó chắc chắn không vượt qua căn bậc 2 của n. Như vậy điều kiện trong vòng for sẽ được đổi thành i <= sqrt(n), nhưng để gọi hàm sqrt() cần phải khai báo thư viện math.h, ép kiểu n sang kiểu thực,... khá rườm rà nên ta có thể đổi thành i*i <= n để tiện hơn.