nlogn
O(nlogn)排序算法
排序算法 介绍常见时间复杂度为\(O(nlogn)\)的排序算法 1. 快速排序 分治思想 #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int a[N]; void quick_sort(int l, in ......
时间复杂度为 O(nlogn) 的排序算法
归并排序遵循分治的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后合并这些子问题的解来建立原问题的解 ......
O(nlogn)复杂度三维偏序
给定三个长为 \(n\) 的序列 \(a, b, c\)，求有多少个二元组 \((i, j)\) 满足 \(a_i < a_j, b_i < b_j, c_i < c_j\)。 \(n \leq 10^6\)。 考虑对 \((a, b), (a, c), (b, c)\) 分别做一次二维偏序，设它们 ......
基于dfn序的O(nlogn)-O(1) lca
\(dfn\)序的长度是欧拉序的一半，常数较小，并且代码便于理解背诵。 让欧拉序求lca成为时代的眼泪。 代码部分实现思路来自cqbz_dongjie 点击查看代码 auto minlca = [&](int x, int y) { return (dfn[x] < dfn[y])? x : y; ......
dfs 序 O(nlogn)-O(1) 求 LCA
学点分树，发现不会询问复杂度 \(O(1)\) 的 LCA。于是被迫递归式学习。 我们设 \(dfn_i\) 表示点 \(i\) 在 dfs 过程中第几个被访问到，把点按访问到的顺序排序得到的序列叫 dfs 序。 考虑 \(u\) 和 \(v\) 在 dfs 序上的位置之间的这一段序列有什么。 设 ......
[算法学习笔记] O(nlogn)求最长上升子序列
### 朴素 dp 求最长上升子序列 大家应该都会朴素 dp 求最长上升子序列，简单回忆一下。 我们令 $f_i$ 表示以 第 $i$ 位元素为结尾的最长上升子序列长度。满足 $\forall j 朴素 dp 求最长上升子序列代码 ```cpp #include #include #include ......
时间复杂度O(1)，O(logn) ，O(n)，O(nlogn)...
## 写在前面 在学习数据结构和算法的时候，经常会碰到O(1),O(n)等等用来表示时间和[空间复杂度](https://so.csdn.net/so/search?q=空间复杂度&spm=1001.2101.3001.7020)，那这到底是什么意思。我们对于同一个问题经常有不同的解决方式，比如排序 ......
大根堆和小根堆在海量数据的top N问题中，时间复杂度O(nlogN)
堆可视化操作演示：https://visualgo.net/zh/heap 堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：小根堆：Key[i]<=key[2i+1]&&Key[i]<=key[2i+2] 或者 大根堆 Key[i]>=Key[2i+1]&&key>=key[2i+2] 即任何一 ......
笔记1. O(NlogN)的排序算法
准备工作 打印数组 void PrintfNums(int *nums, int numsSize) { for (int i = 0; i < numsSize; i++) { printf("%d ", nums[i]); } printf("\n"); } 交换元素 void Swap(int ......