一亿些知识点

经验分享区
1

三角函数：

\sin 正弦: \large\frac{对边}{斜边}
\cos 余弦:\large\frac{邻边}{斜边}
\tan 正切:\large\frac{对边}{邻边}
\log_ab=\log_nb/\log_na

  • 特殊的角度：

特殊角度 \sin \cos \tan
0° 0 1 0
30° \frac{1}{2} \frac{\sqrt{3}}{2} \frac{1}{\sqrt{3}}
45° \frac{\sqrt{2}}{2} \frac{\sqrt{2}}{2} 1
60° \frac{\sqrt{3}}{2} \frac{1}{2} \sqrt{3}
90° 1 0 /

同余：

同余定理：给定一个正整数 m ，如果用 m 去除任意两个整数 a,b 所得的余数相同，则称 a,b 对模 m 同余，记作 a \equiv b(mod\ \ m)
简单地说就是两个或两个以上的整数，除以一个整数 m ，如果它们的余数相同，那么这几个整数对于除数 m 来说就是同余的，即余数相同。

  • 例如：

a\ mod\ 7=1
b\ mod\ 7=1
a\equiv b

排列组合：

\large A_{m}^{n}=\large n\cdot n-1\cdots n-m+1
\large C_{m}^{n}=\large\frac{n\cdot n-1\cdots n-m+1}{m!}
\large C_{m}^{n}=\large\frac{A_{m}^{n}}{m!}

对数函数：

  • 自然对数函数 \ln

以常数 e 为底的对数函数
\ln(x)表示x的自然对数函数，其中x是实数

  • 通用对数函数 \log ：

以常数 10 为底的对数函数
\log(x)表示x的通用函数，其中x是实数

  • 特殊值

\ln(1)=0 \ln(e)=1
\log(1)=0 \log(10)=1

逻辑运算符：

  • 蕴含 \large→

前提为真，结论为真

P Q P→Q
True True True
True False False
False True False
False False True

  • 非 \neg\ \ \ \ !

取反

P \large\neg P
True False
False True

  • 与 \large\wedge\ \ \ \&\&

两个都一样，答案才为真

P Q P \wedge Q
True True True
True False False
False True False
False False False

  • 或 \large\vee\ \ \ \ \|

“耶”或
只要有一个是真,答案就是真

P Q P \vee Q
True True True
True False True
False True True
False False False

归并排序

  • 代码：

#include<bits/stdc++.h>
using namespace std;
int a[10005],b[10005];
void f(int l,int r){
	if(l==r) return;
	int mid=(l+r)/2;
	f(l,mid);
	f(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]<=a[j])
			b[k++]=a[i++];
		else
			b[k++]=a[j++];
	}
	while(i<=mid) b[k++]=a[i++];
	while(j<=r) b[k++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=b[i];
}
int main(){
	int l,r;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	f(1,n);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

  • master 公式:

T(n) = aT(n/b) + O(n^d)

  • 时间复杂度：

1.\large case1:
\large\log_{b}a<d -> O(n^d)
2.\large case2:
\large\log_ba>d -> O(N^{\log_ba})
3.\large case3:
\large\log_ba=d -> O(n^d\times \log\ n)

快速排序：

  • 代码

#include <bits/stdc++.h>
using namespace std;
int a[100005];
void quickSort(int l,int r) {
	if(l >= r)return;
	int temp = a[l];
	int i = l,j = r;
	while(i < j) {
		while(i < j && a[j] > temp)j--;
		a[i] = a[j];
		while(i < j && a[i] <= temp)i++;
		a[j] = a[i];
	}
	a[i] = temp;
	quickSort(l,i - 1);
	quickSort(i + 1,r);
}
int main(int argc,char * argv[]) {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	quickSort(1,n);
	for(int i = 1; i <= n; i++) {
		cout << a[i] << ' ';
	}
	return 0;
}

  • master 公式:

T(n) = aT(n/b) + O(n^d)

  • 时间复杂度：

  • 一般情况：

1.\large case1:
\large\log_{b}a<d -> O(n^d)
2.\large case2:
\large\log_ba>d -> O(N^{\log_ba})
3.\large case3:
\large\log_ba=d -> O(n^d\times \log\ n)

  • 最坏情况：

O(n^2)

1 个赞
2

快排平均 O(nlogn) ，最坏 O(n^2)

2 个赞
3

我认为可以加上对数的换底公式。那个很好用。

2 个赞
4

\log_ab=\log_nb/\log_na
是这个吗
@张瑜

5

Yes。 :grinning: