listC++ Data Structure & Algorithm
ประยุกต์กับ LeetCode
สารบัญ
การสำรวจเวลาและ Memory ที่ใช้ใน LeetCode
สำหรับเว็บ Leet Code ตรงส่วนของ Submission เองจะมีส่วนของการบอกเวลาไว้เหมือนกัน เราสามารถดูส่วนนี้ และเทียบ Code Complexity กับเวลาได้เช่นกัน
เวลา กับ Big O
โจทย์ https://leetcode.com/problems/4sum/description/
code แบบ Time limit Exceed
cpp
class Solution {
public:
vector<vector<int>> fourSum(vector<int> &nums, int target) {
int n = nums.size();
set<vector<int>> quadruplets;
for (int i = 0; i < n - 3; i++) {
for (int j = i + 1; j < n - 2; j++) {
for (int k = j + 1; k < n - 1; k++) {
for (int l = k + 1; l < n; l++) {
if ((long long)nums[i] + nums[j] + nums[k] + nums[l] == target) {
vector<int> quad = {nums[i], nums[j], nums[k], nums[l]};
sort(quad.begin(), quad.end());
quadruplets.insert(quad);
}
}
}
}
}
vector<vector<int>> result(quadruplets.begin(), quadruplets.end());
return result;
}
};วิเคราะห์ Big O จาก code นี้ เมื่อ n คือขนาดของ Array nums
- loop ชั้นนอกสุด วนรอบ n-3 ครั้ง ดังนั้นมีความซับซ้อน O(n)
- loop ชั้นที่ 2 วนรอบ n-2 ครั้ง ดังนั้นมีความซับซ้อน O(n)
- loop ชั้นที่ 3 วนรอบ n-1 ครั้ง ดังนั้นมีความซับซ้อน O(n)
- loop ชั้นในสุด วนรอบ n ครั้ง ดังนั้นมีความซับซ้อน O(n)
เนื่องจากเป็นลูปซ้อนกัน 4 ชั้น ดังนั้นความซับซ้อนรวมของ function fourSum จึงเป็น O(n^4)
จากเคสนี้ส่งผลทำให้เกิดเคส Time Limit Exceed เกิดขึ้นเนื่องจากใช้เวลาการคำนวนที่นานเกินไป (กว่าที่โจทย์กำหนด)
code แบบผ่านเรื่องเวลา
สิ่งที่เราจะทำคือ เราจะพยายามลด Big O ของ code ลง โดย
- การเรียงลำดับ Array nums ใช้เวลา O(n log n) โดยใช้ Algorithm การเรียงลำดับมาตรฐาน เช่น quicksort หรือ mergesort
- มี loop เพียงแค่ 2 loop โดย loop นอกทำงาน n-3 รอบ
- สำหรับแต่ละรอบ loop จะทำงาน n-2-i รอบ โดย i คือ index ของ loop นอก
- loop ใน มี loop while ที่ใช้เทคนิค 2 pointer (เพิ่มตัวชี้ 2 ตัว) เพื่อหาตัวเลขอีกสองตัว ในกรณีที่แย่ที่สุด loop while นี้อาจทำงานได้ถึง O(n) รอบสำหรับแต่ละรอบของ loop ใน
เมื่อรวมสิ่งเหล่านี้เข้าด้วยกัน:
- การเรียงลำดับใช้เวลา O(n log n)
- loop ซ้อนกันมีจำนวนรอบรวมทั้งหมด (n-3) * (n-2) ซึ่งลดรูปได้เป็น O(n^2)
- สำหรับแต่ละรอบของ loop ซ้อน loop while ด้านในใช้เวลา O(n)
ดังนั้น ความซับซ้อนของเวลาโดยรวมคือผลรวมของส่วนเหล่านี้ O(n log n) + O(n^2) * O(n) = O(n log n) + O(n^3)
code ก็จะมีหน้าตาออกมาเป็นแบบนี้แทน
cpp
class Solution {
public:
vector<vector<int>> fourSum(vector<int> &nums, int target) {
int n = nums.size();
vector<vector<int>> result;
if (n < 4) {
return result;
}
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] >
target) {
break;
}
if ((long long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] <
target) {
continue;
}
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
if ((long long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if ((long long)nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
continue;
}
int left = j + 1;
int right = n - 1;
while (left < right) {
long long sum =
(long long)nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
result.push_back({nums[i], nums[j], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
left++;
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return result;
}
};