我要评论
目录
🍉贪心算法
🍈介绍
🍈贪心算法的基本原理
🍈步骤
🍍选择初始状态
- 确定算法的起点。
🍍应用贪心选择性
- 在当前状态下选择一个局部最优的动作，以期望能达到全局最优。
🍍检查算法的可行性
- 判断当前选择是否满足问题的约束条件。
🍍更新状态
- 根据贪心选择的结果更新当前状态。
🍍结束条件
- 检查是否达到算法的结束条件。
🍉经典问题示例
🍈活动选择问题
🍍问题描述
🍍问题分析
🍌解题思路
- 每次选择结束时间最早且与已选择活动不冲突的活动。选择的贪心策略是优先选择结束时间最早的活动。
🍌解题步骤
- 将活动按照结束时间从小到大排序。
- 初始化：选择第一个活动，并将其添加到结果集中。
- 对于每个后续活动，若其开始时间不早于上一个选择的活动的结束时间，则选择该活动。
- 返回结果集中的活动数。
🍌画图解析
活动 : a1 a2 a3 a4 a5 a6
开始时间: 1 2 4 1 5 8
结束时间: 3 5 7 8 9 10
排序后活动: a1 a2 a3 a5 a6 a4
选择顺序: a1 a3 a6
🍍代码实现
🍌源代码
#include <iostream>
#include <vector>
#include <algorithm>
// 活动结构体
struct activity {
int start;
int end;
int index; // 活动的原始索引
};
// 比较器函数，用于按结束时间排序活动
bool compare(activity a, activity b) {
return a.end < b.end;
}
// 贪心算法选择最大数量的非重叠活动
std::vector<int> select_activities(std::vector<activity>& activities) {
// 按结束时间排序活动
std::sort(activities.begin(), activities.end(), compare);
std::vector<int> selected_activities;
int last_end_time = 0;
for (const auto& activity : activities) {
if (activity.start >= last_end_time) {
selected_activities.push_back(activity.index);
last_end_time = activity.end;
}
}
return selected_activities;
}
int main() {
// 定义活动的开始和结束时间
std::vector<activity> activities = {
{1, 3, 1},
{2, 5, 2},
{4, 7, 3},
{1, 8, 4},
{5, 9, 5},
{8, 10, 6}
};
// 选择活动
std::vector<int> selected_activities = select_activities(activities);
// 打印选择的活动
std::cout << "选择的活动顺序: ";
for (int index : selected_activities) {
std::cout << "a" << index << " ";
}
std::cout << std::endl;
return 0;
}
🍌代码解析
🍌运行结果
🍍效率
🍌时间复杂度
因此，总的时间复杂度为：o(nlogn)+o(n)=o(nlogn)
🍌空间复杂度
因此，总的空间复杂度为：o(n)+o(logn)+o(n)=o(n)
🍈哈夫曼编码
🍍问题描述
🍍问题分析
🍌解题思路
- 每次从频率表中选择频率最小的两个字符合并，形成一个新的字符，并更新频率表。重复此操作直到所有字符都被合并。
🍌解题步骤
- 构建一个优先队列，将所有字符及其频率放入队列。
- 从队列中取出频率最小的两个节点，将其合并为一个新的节点，并将合并后的节点重新加入队列。
- 重复步骤2，直到队列中只剩下一个节点，该节点即为哈夫曼树的根节点。
- 通过遍历哈夫曼树生成哈夫曼编码。
🍌画图解析
字符及频率: a:45, b:13, c:12, d:16, e:9, f:5
步骤 1: 取频率最小的 'f' 和 'e'
5 9
| |
f e
步骤 2: 合并 'f' 和 'e'
14
/ \
f e
步骤 3: 取频率最小的 'c' 和 'b'
12 13
| |
c b
步骤 4: 合并 'c' 和 'b'
25
/ \
c b
步骤 5: 取频率最小的 '14' 和 'd'
14 16
/ \ |
f e d
步骤 6: 合并 '14' 和 'd'
30
/ \
14 d
/ \
f e
步骤 7: 取频率最小的 '25' 和 '30'
30 25
/ \ / \
14 d c b
/ \
f e
步骤 8: 合并 '25' 和 '30'
55
/ \
30 25
/ \ / \
14 d c b
/ \
f e
🍍代码实现
🍌源代码(c++)
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
// 节点结构体
struct node {
char character;
int frequency;
node *left, *right;
node(char ch, int freq, node* l = nullptr, node* r = nullptr)
: character(ch), frequency(freq), left(l), right(r) {}
};
// 比较器，用于优先队列
struct compare {
bool operator()(node* l, node* r) {
return l->frequency > r->frequency;
}
};
// 递归生成编码
void generate_codes(node* root, const std::string& str, std::unordered_map<char, std::string>& huffman_codes) {
if (!root) return;
if (!root->left && !root->right) {
huffman_codes[root->character] = str;
}
generate_codes(root->left, str + "0", huffman_codes);
generate_codes(root->right, str + "1", huffman_codes);
}
// 哈夫曼编码主函数
std::unordered_map<char, std::string> huffman_encoding(const std::unordered_map<char, int>& frequencies) {
std::priority_queue<node*, std::vector<node*>, compare> heap;
for (const auto& pair : frequencies) {
heap.push(new node(pair.first, pair.second));
}
while (heap.size() > 1) {
node* left = heap.top(); heap.pop();
node* right = heap.top(); heap.pop();
int sum = left->frequency + right->frequency;
heap.push(new node('\0', sum, left, right));
}
node* root = heap.top();
std::unordered_map<char, std::string> huffman_codes;
generate_codes(root, "", huffman_codes);
return huffman_codes;
}
// 打印哈夫曼编码
void print_huffman_codes(const std::unordered_map<char, std::string>& huffman_codes) {
for (const auto& pair : huffman_codes) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
}
// 测试哈夫曼编码
int main() {
std::unordered_map<char, int> frequencies = { {'a', 45}, {'b', 13}, {'c', 12}, {'d', 16}, {'e', 9}, {'f', 5} };
std::unordered_map<char, std::string> huffman_codes = huffman_encoding(frequencies);
print_huffman_codes(huffman_codes);
return 0;
}
🍌代码解析
🍌运行结果
🍍效率
🍌时间复杂度
结合上述各步骤，哈夫曼编码算法的总体时间复杂度为：o(nlogn)
🍌空间复杂度
结合上述各项，哈夫曼编码算法的总体空间复杂度为：o(n)
🍉贪心算法的优缺点
🍈优点🍈
🍈缺点🍈
🍈适用问题的特性🍈
为了确保贪心算法能够找到问题的最优解，需要满足以下特性
🍈示例🍈
🍉总结
希望这些能对刚学习算法的同学们提供些帮助哦！！！
发表评论