- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
持续更新数据结构与算法专题,欢迎关注....... 。
定义 。
在数学和计算机科学领域,算法是一系列有限的严谨指令,通常用于解决一类特定问题或执行计算 。
In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.[^1] 。
Introduction to Algorithm[^2] 。
不正式的说,算法就是任何定义优良的计算过程:接收一些值作为输入,在有限的时间内,产生一些值作为输出.
Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output in a finite amount of time. 。
定义 。
在计算机科学领域,数据结构是一种数据组织、管理和存储格式,通常被选择用来高效访问数据 。
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data 。
Introduction to Algorithm[^2] 。
数据结构是一种存储和组织数据的方式,旨在便于访问和修改 。
A data structure is a way to store and organize data in order to facilitate access and modifications 。
可以说,程序 = 数据结构 + 算法,它们是每一位程序员的基本功,下来我们通过对一个非常著名的二分查找算法的讲解来认识一下算法 。
二分查找算法也称折半查找,是一种非常高效的工作于有序数组的查找算法。后续的课程中还会学习更多的查找算法,但在此之前,不妨用它作为入门.
需求:在有序数组 \(A\) 内,查找值 \(target\) 。
算法描述 。
前提 | 给定一个内含 \(n\) 个元素的有序数组 \(A\),满足 \(A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}\),一个待查值 \(target\) |
1 | 设置 \(i=0\),\(j=n-1\) |
2 | 如果 \(i \gt j\),结束查找,没找到 |
3 | 设置 \(m = floor(\frac {i+j}{2})\) ,\(m\) 为中间索引,\(floor\) 是向下取整(\(\leq \frac {i+j}{2}\) 的最小整数) |
4 | 如果 \(target < A_{m}\) 设置 \(j = m - 1\),跳到第2步 |
5 | 如果 \(A_{m} < target\) 设置 \(i = m + 1\),跳到第2步 |
6 | 如果 \(A_{m} = target\),结束查找,找到了 |
P.S. 。
- 对于一个算法来讲,都有较为严谨的描述,上面是一个例子
- 后续讲解时,以简明直白为目标,不会总以上面的方式来描述算法
java 实现 。
public static int binarySearch(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) { // 在左边
j = m - 1;
} else if (a[m] < target) { // 在右边
i = m + 1;
} else {
return m;
}
}
return -1;
}
另一种写法 。
public static int binarySearch(int[] a, int target) {
int i = 0, j = a.length;
while (i < j) {
int m = (i + j) >>> 1;
if (target < a[m]) { // 在左边
j = m;
} else if (a[m] < target) { // 在右边
i = m + 1;
} else {
return m;
}
}
return -1;
}
时间复杂度 。
下面的查找算法也能得出与之前二分查找一样的结果,那你能说出它差在哪里吗?
public static int search(int[] a, int k) {
for (
int i = 0;
i < a.length;
i++
) {
if (a[i] == k) {
return i;
}
}
return -1;
}
考虑最坏情况下(没找到)例如 [1,2,3,4] 查找 5 。
int i = 0
只执行一次i < a.length
受数组元素个数 \(n\) 的影响,比较 \(n+1\) 次i++
受数组元素个数 \(n\) 的影响,自增 \(n\) 次a[i] == k
受元素个数 \(n\) 的影响,比较 \(n\) 次return -1
,执行一次粗略认为每行代码执行时间是 \(t\),假设 \(n=4\) 那么 。
如果套用二分查找算法,还是 [1,2,3,4] 查找 5 。
public static int binarySearch(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) { // 在左边
j = m - 1;
} else if (a[m] < target) { // 在右边
i = m + 1;
} else {
return m;
}
}
return -1;
}
int i = 0, j = a.length - 1 各执行 1 次 。
i <= j 比较 \(floor(\log_{2}(n)+1)\) 再加 1 次 。
(i + j) >>> 1 计算 \(floor(\log_{2}(n)+1)\) 次 。
接下来 if() else if() else 会执行 \(3* floor(\log_{2}(n)+1)\) 次,分别为 。
return -1,执行一次 。
结果:
注意:
左侧未找到和右侧未找到结果不一样,这里不做分析 。
两个算法比较,可以看到 \(n\) 在较小的时候,二者花费的次数差不多 。
但随着 \(n\) 越来越大,比如说 \(n=1000\) 时,用二分查找算法(红色)也就是 \(54t\),而蓝色算法则需要 \(3003t\) 。
画图采用的是 Desmos | 图形计算器 。
计算机科学中,时间复杂度是用来衡量:一个算法的执行,随数据规模增大,而增长的时间成本 。
如何表示时间复杂度呢?
假设算法要处理的数据规模是 \(n\),代码总的执行行数用函数 \(f(n)\) 来表示,例如:
为了对 \(f(n)\) 进行化简,应当抓住主要矛盾,找到一个变化趋势与之相近的表示法 。
大 \(O\) 表示法[^4] 。
其中 。
渐进上界 。
渐进上界(asymptotic upper bound):从某个常数 \(n_0\)开始,\(c*g(n)\) 总是位于 \(f(n)\) 上方,那么记作 \(O(g(n))\) 。
例1 。
例2 。
已知 \(f(n)\) 来说,求 \(g(n)\) 。
常见大 \(O\) 表示法 。
按时间复杂度从低到高 。
渐进下界 。
渐进下界(asymptotic lower bound):从某个常数 \(n_0\)开始,\(c*g(n)\) 总是位于 \(f(n)\) 下方,那么记作 \(\Omega(g(n))\) 。
渐进紧界 。
渐进紧界(asymptotic tight bounds):从某个常数 \(n_0\)开始,\(f(n)\) 总是在 \(c_1*g(n)\) 和 \(c_2*g(n)\) 之间,那么记作 \(\Theta(g(n))\) 。
空间复杂度 。
与时间复杂度类似,一般也使用大 \(O\) 表示法来衡量:一个算法执行随数据规模增大,而增长的额外空间成本 。
public static int binarySearchBasic(int[] a, int target) {
int i = 0, j = a.length - 1; // 设置指针和初值
while (i <= j) { // i~j 范围内有东西
int m = (i + j) >>> 1;
if(target < a[m]) { // 目标在左边
j = m - 1;
} else if (a[m] < target) { // 目标在右边
i = m + 1;
} else { // 找到了
return m;
}
}
return -1;
}
二分查找性能 。
下面分析二分查找算法的性能 。
时间复杂度 。
空间复杂度 。
public static int binarySearchBalance(int[] a, int target) {
int i = 0, j = a.length;
while (1 < j - i) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m;
} else {
i = m;
}
}
return (a[i] == target) ? i : -1;
}
思想:
private static int binarySearch0(long[] a, int fromIndex, int toIndex,
long key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
long midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
有时我们希望返回的是最左侧的重复元素,如果用 Basic 二分查找 。
对于数组 \([1, 2, 3, 4, 4, 5, 6, 7]\),查找元素4,结果是索引3 。
对于数组 \([1, 2, 4, 4, 4, 5, 6, 7]\),查找元素4,结果也是索引3,并不是最左侧的元素 。
public static int binarySearchLeftmost1(int[] a, int target) {
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m; // 记录候选位置
j = m - 1; // 继续向左
}
}
return candidate;
}
如果希望返回的是最右侧元素 。
public static int binarySearchRightmost1(int[] a, int target) {
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m; // 记录候选位置
i = m + 1; // 继续向右
}
}
return candidate;
}
应用 。
对于 Leftmost 与 Rightmost,可以返回一个比 -1 更有用的值 。
Leftmost 改为 。
public static int binarySearchLeftmost(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target <= a[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i;
}
Rightmost 改为 。
public static int binarySearchRightmost(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i - 1;
}
几个名词 。
范围查询:
求排名:\(leftmost(target) + 1\) 。
求前任(predecessor):\(leftmost(target) - 1\) 。
求后任(successor):\(rightmost(target)+1\) 。
求最近邻居:
用函数 \(f(n)\) 表示算法效率与数据规模的关系,假设每次解决问题需要 1 微秒(\(10^{-6}\) 秒),进行估算:
参考解答 。
一台机器对200个单词进行排序花了200秒(使用冒泡排序),那么花费800秒,大概可以对多少个单词进行排序 。
a. 400 。
b. 600 。
c. 800 。
d. 1600 。
答案 。
解释 。
要点:减而治之,可以用递归或非递归实现 。
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1 。
例如 。
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
参考答案:略,可以用讲过的任意一种二分求解 。
要点:理解谁代表插入位置 。
给定一个排序数组和一个目标值 。
例如 。
输入: nums = [1,3,5,6], target = 5
输出: 2
输入: nums = [1,3,5,6], target = 2
输出: 1
输入: nums = [1,3,5,6], target = 7
输出: 4
参考答案1:用二分查找基础版代码改写,基础版中,找到返回 m,没找到 i 代表插入点,因此有 。
public int searchInsert(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
return m;
}
}
return i; // 原始 return -1
}
参考答案2:用二分查找平衡版改写,平衡版中 。
public static int searchInsert(int[] a, int target) {
int i = 0, j = a.length;
while (1 < j - i) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m;
} else {
i = m;
}
}
return (target <= a[i]) ? i : i + 1;
// 原始 (target == a[i]) ? i : -1;
}
参考答案3:用 leftmost 版本解,返回值即为插入位置(并能处理元素重复的情况) 。
public int searchInsert(int[] a, int target) {
int i = 0, j = a.length - 1;
while(i <= j) {
int m = (i + j) >>> 1;
if(target <= a[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i;
}
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置.
如果数组中不存在目标值 target,返回 [-1, -1].
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题 。
例如 。
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
输入:nums = [], target = 0
输出:[-1,-1]
参考答案 。
public static int left(int[] a, int target) {
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m;
j = m - 1;
}
}
return candidate;
}
public static int right(int[] a, int target) {
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m;
i = m + 1;
}
}
return candidate;
}
public static int[] searchRange(int[] nums, int target) {
int x = left(nums, target);
if(x == -1) {
return new int[] {-1, -1};
} else {
return new int[] {x, right(nums, target)};
}
}
本文,已收录于,我的技术网站 pottercoding.cn,有大厂完整面经,工作技术,架构师成长之路,等经验分享.
最后此篇关于初识算法的文章就讲到这里了,如果你想了解更多关于初识算法的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
滑动窗口限流 滑动窗口限流是一种常用的限流算法,通过维护一个固定大小的窗口,在单位时间内允许通过的请求次数不超过设定的阈值。具体来说,滑动窗口限流算法通常包括以下几个步骤: 初始化:设置窗口
表达式求值:一个只有+,-,*,/的表达式,没有括号 一种神奇的做法:使用数组存储数字和运算符,先把优先级别高的乘法和除法计算出来,再计算加法和减法 int GetVal(string s){
【算法】前缀和 题目 先来看一道题目:(前缀和模板题) 已知一个数组A[],现在想要求出其中一些数字的和。 输入格式: 先是整数N,M,表示一共有N个数字,有M组询问 接下来有N个数,表示A[1]..
1.前序遍历 根-左-右的顺序遍历,可以使用递归 void preOrder(Node *u){ if(u==NULL)return; printf("%d ",u->val);
先看题目 物品不能分隔,必须全部取走或者留下,因此称为01背包 (只有不取和取两种状态) 看第一个样例 我们需要把4个物品装入一个容量为10的背包 我们可以简化问题,从小到大入手分析 weightva
我最近在一次采访中遇到了这个问题: 给出以下矩阵: [[ R R R R R R], [ R B B B R R], [ B R R R B B], [ R B R R R R]] 找出是否有任
我正在尝试通过 C++ 算法从我的 outlook 帐户发送一封电子邮件,该帐户已经打开并记录,但真的不知道从哪里开始(对于 outlook-c++ 集成),谷歌也没有帮我这么多。任何提示将不胜感激。
我发现自己像这样编写了一个手工制作的 while 循环: std::list foo; // In my case, map, but list is simpler auto currentPoin
我有用于检测正方形的 opencv 代码。现在我想在检测正方形后,代码运行另一个命令。 代码如下: #include "cv.h" #include "cxcore.h" #include "high
我正在尝试模拟一个 matlab 函数“imfill”来填充二进制图像(1 和 0 的二维矩阵)。 我想在矩阵中指定一个起点,并像 imfill 的 4 连接版本那样进行洪水填充。 这是否已经存在于
我正在阅读 Robert Sedgewick 的《C++ 算法》。 Basic recurrences section it was mentioned as 这种循环出现在循环输入以消除一个项目的递
我正在思考如何在我的日历中生成代表任务的数据结构(仅供我个人使用)。我有来自 DBMS 的按日期排序的任务记录,如下所示: 买牛奶(18.1.2013) 任务日期 (2013-01-15) 任务标签(
输入一个未排序的整数数组A[1..n]只有 O(d) :(d int) 计算每个元素在单次迭代中出现在列表中的次数。 map 是balanced Binary Search Tree基于确保 O(nl
我遇到了一个问题,但我仍然不知道如何解决。我想出了如何用蛮力的方式来做到这一点,但是当有成千上万的元素时它就不起作用了。 Problem: Say you are given the followin
我有一个列表列表。 L1= [[...][...][.......].......]如果我在展平列表后获取所有元素并从中提取唯一值,那么我会得到一个列表 L2。我有另一个列表 L3,它是 L2 的某个
我们得到二维矩阵数组(假设长度为 i 和宽度为 j)和整数 k我们必须找到包含这个或更大总和的最小矩形的大小F.e k=7 4 1 1 1 1 1 4 4 Anwser是2,因为4+4=8 >= 7,
我实行 3 类倒制,每周换类。顺序为早类 (m)、晚类 (n) 和下午类 (a)。我固定的订单,即它永远不会改变,即使那个星期不工作也是如此。 我创建了一个函数来获取 ISO 周数。当我给它一个日期时
假设我们有一个输入,它是一个元素列表: {a, b, c, d, e, f} 还有不同的集合,可能包含这些元素的任意组合,也可能包含不在输入列表中的其他元素: A:{e,f} B:{d,f,a} C:
我有一个子集算法,可以找到给定集合的所有子集。原始集合的问题在于它是一个不断增长的集合,如果向其中添加元素,我需要再次重新计算它的子集。 有没有一种方法可以优化子集算法,该算法可以从最后一个计算点重新
我有一个包含 100 万个符号及其预期频率的表格。 我想通过为每个符号分配一个唯一(且前缀唯一)的可变长度位串来压缩这些符号的序列,然后将它们连接在一起以表示序列。 我想分配这些位串,以使编码序列的预
我是一名优秀的程序员,十分优秀!