Brute Force 蛮力法

A Stellar Hiker

2014-12-22

Algorithm, C++, leetcode

是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。
蛮力法的第一个应用就是得出一个算法，此算法可以通过适度的努力来提升它的性能。

选择排序

问题描述

为一个数组排序。

算法描述

第一遍遍历从1到n的n个元素，将找到的最小元素与位置1的元素交换。第二遍遍历从2到n的n-1个元素，将找到的最小元素与位置2的元素交换。以此类推。n-1遍后，该列表就排好序了。

分析

时间复杂度： $O(n^2)$ ，空间复杂度 $O(1)$

代码

// 假设列表是数组
#include <iostream>
void swap(int& a, int& b)
{
	if (a == b) return;
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
}
void print_array(int* A, int n)
{
	for (int i = 0; i < n; ++i)
	{
		std::cout<<A[i]<<" ";
	}
	std::cout<<std::endl;
}
void selection_sort(int* A, int n)
{
	for (int i = 0; i < (n - 1); ++i)
	{
		int min_index(i);
		for (int j = i + 1; j < n; ++j)
		{
			if (A[j] < A[min_index]) {min_index = j;}
		}
		swap(A[i], A[min_index]);
	}
}
int main()
{
	int A[7] = {89, 45, 68, 90, 29, 34, 17};
	selection_sort(A, 7);
	print_array(A, 7);
	system("Pause");
}

冒泡排序

问题描述

为一个数组排序。

算法描述

每次遍历比较表中的相邻元素，如果它们是逆序的话就交换它们的位置。重复n-1次后，列表即排好序。

分析

时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$

代码

// 假设列表是数组
void buble_sort(int* A, int n)
{
	for (int i = n-1; i > 0; --i)
	{
		for (int j = 0; j < i; ++j)
		{
			if (A[j] > A[j+1]) {swap(A[j], A[j+1]);}
		}
	}
}

顺序查找

问题描述

在一个给定的列表中查找一个给定的值。

算法描述

简单地将给定列表中的连续元素和给定的查找键进行比较，直到遇到一个匹配的元素（成功查找），或者在碰到匹配元素前就遍历了整个列表（失败查找）。

分析

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$

代码

int sequential_search(int* A, int n, int k)
{
	int i(0);
	while (i < n && A[i] != k)
	{++i;}
	if (i < n){return i;}
	else{return -1;}
}

蛮力字符串匹配

问题描述

给定一个n个字符组成的串，称为文本。一个m(m<=n)个字符的串，称为模式，从文本中寻找匹配模式的子串。

算法描述

将模式对准文本的前m个字符，然后从左到右匹配每一对相应的字符，直到m对字符全部匹配（算法停止）或者遇到一对不匹配的字符。在后一种情况下，模式右移1位，然后从模式的第一个字符开始，继续把模式和文本中的对应字符进行比较。注意最后一轮子串匹配的起始位置是n-m。

leetcode上的相同题目：[strings] | Implement strStr()

分析

时间复杂度：最坏情况下，每次移动模式之前都做足m次比较，n-m+1次尝试都遇到这种情况，O(nm)。平均情况下，随机文本，O(n+m) = O(n)。
同问题的更高效算法见时空权衡。

代码

int brute_force_string_match(std::string text, std::string pattern)
{
	if (pattern.empty()) return 0;
	if (text.empty()) return -1;
	if(pattern.size() > text.size()) return -1;
	for (int i = 0; i < text.size() - pattern.size()+1; ++i)
	{
		for (int j = 0; j < pattern.size(); ++j)
		{
			if (pattern[j] != text[i+j]) break;
			if (j == pattern.size()-1) return i;
		}
	}
	return -1;
}

[1] 算法设计与分析基础(第2版)
[2] leetcode

选择排序

冒泡排序

顺序查找

蛮力字符串匹配

Leetcode相关题目