So sánh tìm max bằng nhị phân năm 2024
|
CodeLearn is an online platform that helps users to learn, practice coding skills and join the online coding contests. LinksLearning Training Fights InformationAbout Us Terms of Use HelpHelp Discussion Powered by CodeLearn © 2024. All Rights Reserved. rev 2/5/2024 5:31:56 PM chuyenhalong.ucode.vn cung cấp các khóa học lập trình tương tác với Python, Scratch, C/C++, Pascal, Game, Thuật toán, Web, Ứng dụng di động… cho tất cả mọi lứa tuổi, từ học sinh tiểu học đến người đi làm. Các khóa học được biên soạn bởi các chuyên gia giàu kinh nghiệm với những video, bài giảng tương tác, bài tập trực quan và những dự án thực tế. Tất cả đều được thực hiện ngay trên trình duyệt web của bạn. Tìm minDistance trong strip[]. Bước này mới nhìn có vẽ tốn O(n^2) nhưng thực chất chỉ cần O(n), vì mỗi điểm ta chỉ cần tìm khoản cách với 5 đến 7 hàng xóm gần nhất của nó. Bước 7. So sánh d và minDistance để tìm lời giải cuối cùng. Thuật toán trên thể hiện bằng mã C++ như sau: // A divide and conquer program in C++ // to find the smallest distance from a // given set of points. include using namespace std; // A structure to represent a Point in 2D plane class Point { public: int x, y; }; /* Following two functions are needed for library function qsort(). Refer: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */ // Needed to sort array of points // according to X coordinate int compareX(const void* a, const void* b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->x - p2->x); } // Needed to sort array of points according to Y coordinate int compareY(const void* a, const void* b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->y - p2->y); } // A utility function to find the // distance between two points float dist(Point p1, Point p2) { return sqrt( (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y) ); } // A Brute Force method to return the // smallest distance between two points // in P[] of size n float bruteForce(Point P[], int n) { float min = FLT_MAX; for (int i = 0; i < n; ++i) for (int j = i+1; j < n; ++j) if (dist(P[i], P[j]) < min) min = dist(P[i], P[j]); return min; } // A utility function to find // minimum of two float values float min(float x, float y) { return (x < y)? x : y; } // A utility function to find the // distance between the closest points of // strip of given size. All points in // strip[] are sorted according to // y coordinate. They all have an upper // bound on minimum distance as d. // Note that this method seems to be // a O(n^2) method, but it's a O(n) // method as the inner loop runs at most 6 times float stripClosest(Point strip[], int size, float d) { float min = d; // Initialize the minimum distance as d qsort(strip, size, sizeof(Point), compareY); // Pick all points one by one and try the next points till the difference // between y coordinates is smaller than d. // This is a proven fact that this loop runs at most 6 times for (int i = 0; i < size; ++i) for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) if (dist(strip[i],strip[j]) < min) min = dist(strip[i], strip[j]); return min; } // A recursive function to find the // smallest distance. The array P contains // all points sorted according to x coordinate float closestUtil(Point P[], int n) { // If there are 2 or 3 points, then use brute force if (n <= 3) return bruteForce(P, n); // Find the middle point int mid = n/2; Point midPoint = P[mid]; // Consider the vertical line passing // through the middle point calculate // the smallest distance dl on left // of middle point and dr on right side float dl = closestUtil(P, mid); float dr = closestUtil(P + mid, n - mid); // Find the smaller of two distances float d = min(dl, dr); // Build an array strip[] that contains // points close (closer than d) // to the line passing through the middle point Point strip[n]; int j = 0; for (int i = 0; i < n; i++) if (abs(P[i].x - midPoint.x) < d) strip[j] = P[i], j++; // Find the closest points in strip. // Return the minimum of d and closest // distance is strip[] return min(d, stripClosest(strip, j, d) ); } // The main function that finds the smallest distance // This method mainly uses closestUtil() float closest(Point P[], int n) { qsort(P, n, sizeof(Point), compareX); // Use recursive function closestUtil() // to find the smallest distance return closestUtil(P, n); } // Driver code int main() { Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}}; int n = sizeof(P) / sizeof(P[0]); cout << "The smallest distance is " << closest(P, n); return 0; } // Nguồn: This code is contributed by rathbhupendra dẫn từ GeeksforGeeks.com Độ phức tạp: Gọi thời gian thực hiện giải tuật là T(n).
Tổng: T(n) = 2T(n/2) + O(n) + O(nlogn) + O(n) \= 2T(n/2) + O(nlogn) \= T(n*logn*logn) Đề dễ hiểu bước biến đổi này, chúng ta hình dung độ phực tạp của bước sắp xếp mảng strip[], quá trình này lặp lại mỗi level khi ta gộp mảng trong quá trình chia để trị (logn bước) nên tổng thời giản là O(logn*nlogn) = O(n(logn)^2) |
