Cài đặt: Tìm min max của 1 dãy n số với độ phức tạp thuật toán là 3n/2

Xem vấn đề tại đây

Code C:

#include <stdio.h>
#include <conio.h>

#define MAX_INT (2147483647)
#define MIN_INT (-2147483647)

void FindMinMax(int* a, int n, int& min, int& max)
{
	min = MAX_INT;
	max = MIN_INT;
	int minLocal, maxLocal;
	int i, m = n - 1;
	for (i = 0; i < m; i += 2)
	{
		if (a[i] < a[i + 1])
		{
			minLocal = a[i];
			maxLocal = a[i + 1];
		}
		else
		{
			minLocal = a[i + 1];
			maxLocal = a[i];
		}
		if (minLocal < min) min = minLocal;
		if (maxLocal > max) max = maxLocal;
	}
	if (i == m)
	{
		if (a[i] < min) min = a[i];
		if (a[i] > max) max = a[i];
	}
}

void main()
{
	const int n = 11;
	int a[n] = {100, 2, 3, 400, 5, 6, 7, -8, 9, 10, -777};
	int min, max;
	FindMinMax(a, n, min, max);
	printf("min, max = %d, %d", min, max);
	getch();
}
Advertisements

2 thoughts on “Cài đặt: Tìm min max của 1 dãy n số với độ phức tạp thuật toán là 3n/2

  1. 1) Số phép so sánh đúng là 3n/2 nhưng số phép assignment vẫn có thể là 2n, vậy nên tiêu đề về độ phức tạp là chưa đúng.

    2) Implementation này không giống với vấn đề được trình bày trong link của bạn. Vì nếu implement như đã trình bày, mình phải đệ quy để tìm cặp (min max) của n/2 cặp, n/4 cặp, vv.

    3) Ý tưởng hay!

    Liked by 1 person

  2. Lúc tìm cách giải thì tớ chưa nghĩ đến chuyện cài đặt. Nhưng gần đây nghĩ lại thấy có cách cài đặt ko cần đệ quy. Nói chung, dù là cách gì đi nữa thì mấu chốt vẫn là ở chỗ: tìm min max 2 số chỉ mất 1 phép so sánh.

    Cám ơn cả 3 nhận xét của bạn.

    Thân ái.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s