AKSZ-算法入门

userId_undefined

zcc

倔强青铜

2024-03-10 17:59:43

发布于：广东

8阅读
0回复
0点赞

算法入门

1.算法的特征

1.有穷性

2.确切性

3.输入项

4.输出项

5.可行性

2.求和公式

1+2+...+n1+2+...+n

(1+n)∗n/2(1+n)*n/2

3.时间频度 T(n)

一个算法的语句执行的次数称为语句频率或者时间频度，表示为T(n)T(n)

T(n)=3∗n+4T(n)=3*n+4

4.时间复杂度O(n)

1.常见排序

  • 选择排序 O(n^2)
  • 冒泡排序 O(n^2)
  • 插入排序 O(n^2)
  • 桶排序 O(n+k)

桶排序代码如下：

int n;
cin>>n;
for(int i=0;i<n;++i){
	int x;
	cin>>x;
	a[x]++;
}
for(int i=0;i<=k;++i){
	for(int i=0;i<=k;++i){
		cout<<i;
	}
}

2.常见时间复杂度

O(1),O(logn),O(n),O(nlogn),O(n2),O(n3),O(2n),O(n!).O(1),O(logn),O(n),O(nlogn),O(n^2),O(n^3),O(2^n),O(n!).

3.运算量随着规模的变化

运算量 n!n! 2n2^n n3n^3 n2n^2 nlog2nnlog_2n nn
最大规模 11 26 464 10^4 4.5*10^6 10^8
速度扩大 11 27 584 14142 8.6*10^6 2*10^8

5.空间复杂度(256M)

longlong long=>3.2∗107long =>3.2*10^7

int=>6.4∗107int=>6.4*10^7

6.对数

  • a∗a∗...∗a=>ax=Na*a*...*a=>a^x=N
  • x=logaNx=log_aN

7.模拟算法

1.审题立意

不遗漏 分析题目样例

2.分析关系

最好用流程图或简单表格列出

3.编写程序

用相应的语言、逐步求精的方法描述具体的算法

4.调试运行

输出中间重要过程

5.构造数据

构造一些更复杂、更全面的测试数据来检查程序的正确性

8.如何让程序正确性更高——对拍

对拍代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	while(1){
		system("数据.exe>test.in");
		system("正解代码.exe<test.in>my.out");
		system("暴力.exe<test.in>std.out");
		if(system("fc my.out std.out")){//返回非0表示有差异
			system("pause");
		}
	}
	return 0;
}

缺点：1.只要求输出正解；2.数据范围过大

userId_undefined
去预览
0/2000

全部评论 1

热门讨论