算法分析
第一次
程序设计一般步骤
1 确定数据结构
2 确定算法
3 编写程序
4 调试程序
5 编写文档资料
上述5个步骤中最重要的第2步 确定算法
算法：所谓算法是指某个问题或者某个功能的求解方法。
实际中某个问题或者某个功能的求解方法不止一个。
考虑选择哪种算法作为我该问题或者该功能的最终解决方案呢？
1 算法正确
2 时间复杂度和空间复杂度
例1 输入一个正整数给x，判断其是否是素数？
分析 所谓素数就是质数：也就是只能被1和其本身（x）整除的数
其实任何额一个正整数都能被1和其本身整除，而这点其实可以不证明
重点去证明：不能被2到x-1范围内的所有的数整除。
举例：
x=7 2 3 4 5 6
2到6中每个数值都与7之间是不能整除的关系，所以7才是素数
x=8 2 3 4 5 6 7
8对2取余数就是0，整除关系，结果可以直接下结论8不是3到7就没必要再进行判断了，循环可以提前结束。
整个问题中涉及2个问题，是素数1，不是素数0
代码1
#include"stdio.h"
#include"windows.h"
int main()
{
int x,i,flag;//flag=1 是素数 flag=0 表示不是素数
printf(“请你任意输入一个正整数:”);
scanf("%d",&x);
flag=1;//相当于一开始假设x是素数
for(i=2;i<=x-1;i++)
{
if(x%i==0)
{
flag=0;
break;
}
}
if(flag==1)
printf(“yes”);
else
printf(“no”);
system(“pause”);
}
上述程序的时间复杂度是多少？ o(n)
时间复杂度的表示形式是 o(?)
1 白话解释：看程序运行所耗费的时间
2 专业理解：形式o(?)
？体现出来的就是一个问题求解过程中操作的执行次数。
执行次数要把问题放大到n个数值的角度来看待。
特别注意： 专业理解时间复杂度的问题，把一个问题求解方法的过程，放大到n个数值类似的角度来看待问题。
举例说明：s=1+2+3+4+…+100
方法1 用等差数列求和公式来表示
s=(1+100)*100/2;
时间复杂度 o(1)
注意这里1 表示操作的执行次数
方法2 用循环
s=0;
for(i=1;i<=100;i++)
s=s+i;
时间复杂度 o(n)
注意这里n 表示操作的执行次数
如果在之前所学过的输出所有三位数值中的水仙花数。
for(a=1;a<=9;a++)
for(b=0;c<=9;b++)
for(c=0;c<=9;c++)
{
t=a100+b10+c;
if(t==aaa+bbb+ccc)
printf("%d\n",t);
}
白话解释 91010
时间复杂度 o(nnn) 等价 o(n^3)
改进素数程序
举例
x=7 2 3 4 5 6 2到6中每个数值都与7之间是不能整除的关系，所以7才是素数
x=8 2 3 4 5 6 7 8对2取余数就是0，整除关系，结果可以直接下结论8不是
3到7就没必要再进行判断了。
循环可以提前结束。
注意 上述方法中
其实对于7而言 4 5 6没必要判断，因为它们都超过了7的一半，所以不可能是整除关系
其实对于8而言 5 6 7没必要判断，因为它们都超过了8的一半，所以不可能是整除关系
最后修改的是循环 for(i=2;i<=x/2;i++)
代码2
#include"stdio.h"
#include"windows.h"
int main()
{
int x,i,flag;//flag=1 是素数 flag=0 表示不是素数
printf(“请你任意输入一个正整数:”);
scanf("%d",&x);
flag=1;//相当于一开始假设x是素数
for(i=2;i<=x/2;i++)
{
if(x%i==0)
{
flag=0;
break;
}
}
if(flag==1)
printf(“yes”);
else
printf(“no”);
system(“pause”);
}
白话理解：运算次数少了
专业理解：时间复杂度是多少呢？ o(n)
继续修改
4不是素数 因为2
6不是素数 因为2
8不是素数 因为2
9不是素数 因为3
10不是素数 因为2
12不是素数 因为2
14不是素数 因为2
15不是素数 因为3
16不是素数 因为2
。。。。。。。。。。。
25不是素数 因为5
26不是素数 因为2
所以每个数值x是否是素数，判断范围还可以缩小，2到x的平方根 sqrt(x)
代码2
#include"stdio.h"
#include"windows.h"
#include"math.h"
int main()
{
int x,i,flag;//flag=1 是素数 flag=0 表示不是素数
printf(“请你任意输入一个正整数:”);
scanf("%d",&x);
flag=1;//相当于一开始假设x是素数
for(i=2;i<=sqrt(x);i++)
{
if(x%i==0)
{
flag=0;
break;
}
}
if(flag==1)
printf(“yes”);
else
printf(“no”);
system(“pause”);
return 0;
}
白话理解：运算次数少了
专业理解：时间复杂度是多少呢？ o(logn)
最后提醒一下
一般我们强调某个方法的时间复杂度，应该是包含该问题求解方法的所有步骤所耗费的时间
实际处理的是一个问题求解方法中，所有步骤中取耗费时间（次数）最多的作为最后的时间复杂度的描述
一般情况下，时间复杂度的表示形式如下常见的5种
1 o(1)
2 o(n)
3 o(logn)
4 o(n*logn)
5 o(n^3) 或者 o(n^?)
例2 1-1000这1000个数放在含有1001个元素的数组中,只有唯一的一个元素值重复，
其他均只出现一次。设计一个算法，将它找出来，你能否设计一个算法实现?
最后要找出哪个数是重复的？如果可以的话再找出具体是哪2个位置的数?
方法1 简单粗暴，我想用枚举法，暴力破解法。好处，理解简单啊
a[1]???? a[2] ????a[3] ????a[4]???? a[5]???? a[6] ????a[7]???? a[8]???? a[9] ????a[10]???? a[11]
2 ????????9???????? 8 ????????6???????? 5 ????????4???????? 1???????? 3 ????????7 ????????10???????? 8
最终考虑到是任意输入的情况
（1）将a[1]与 a[2]到a[11]依次比较，如果相等则输出a[1]，1，另外一个相同值的位置
for(i=2;i<=11;i++)
{
if(a[1]==a[i])
printf("%d %d %d\n",a[1],1,i);
}
（2）将a[2]与 a[3]到a[11]依次比较，如果相等则输出a[2]，2，另外一个相同值的位置
for(i=3;i<=11;i++)
{
if(a[2]==a[i])
printf("%d %d %d\n",a[2],2,i);
}
…
（10）将a[10]与 a[11]到a[11]依次比较，如果相等则输出a[10]，10，另外一个相同值的位置
for(i=11;i<=11;i++)
{
if(a[10]==a[i])
printf("%d %d %d\n",a[10],10,i);
}
上述过程再凑循环
for(j=1;j<=10;j++)
{
for(i=j+1;i<=11;i++)
{
if(a[j]==a[i])
printf("%d %d %d\n",a[j],j,i);
}
}
最后代码
#include"stdio.h"
#include"windows.h"
int main()
{
int a[12],i,j;
printf(“请你输入11个数值，且在1-10之间，且只能有一个数值重复\n”);
for(i=1;i<=11;i++)
scanf("%d",&a[i]);
for(j=1;j<=10;j++)
{
for(i=j+1;i<=11;i++)
{
if(a[j]==a[i])
printf("%d %d %d\n",a[j],j,i);
}
}
system(“pause”);
}
这里是算次数
10+9+…+1
n-1+n-2+…+1
(n-1+1)(n-1)/2
n(n-1)/2
n^2-n/2
标准 o(1+n+(n^2-n)/2)
这里1 是定义代码的
这里n 是输入代码的
这里(n^2-n)/2 是求解代码的
最后取最大值 o(n^2)
最后的修改思路
a[1]???? a[2] ????a[3] ????a[4]???? a[5]???? a[6] ????a[7]???? a[8]???? a[9] ????a[10]???? a[11]
2 ????????9???????? 8 ????????6???????? 5 ????????4???????? 1???????? 3 ????????7 ????????10???????? 8
准备2个数组，一个数组长度11，另外一个数组长度10
数组a的每个数组元素的值，作为数组b数组元素的标号
数组b中所有数组元素初始值为0
b[1]???? b[2] ???? b[3] ???? b[4]???? b[5] ???? b[6] ???? b[7] ???? b[8] ???? b[9]???? b[10]
1???????? 1 ?????????1?????????? 1???????? 1???????? 1 ???????? 1 ???????? 2???????? 1 ???????? 1
??????????说明2出现了1次 ???????????????????????????????????????????????????????? 说明8出现了2次
#include"stdio.h"
#include"windows.h"
int main()
{
int a[12],b[12]={0},i,j,t;
printf(“请你输入11个数值，且在1-10之间，且只能有一个数值重复\n”);
for(i=1;i<=11;i++)
scanf("%d",&a[i]);
for(i=1;i<=11;i++)
{
b[a[i]]++;
if(b[a[i]]==2)
{
t=a[i];
break;
}
}
//如果输出既要位置也要输出的值，我得再来 一轮循环
for(i=1;i<=11;i++)
{
if(t==a[i])
printf(“相同值%d 相同位置%d\n”,t,i);
}
system(“pause”);
}
其实这个方法是用来 空间换时间。
最后问题该方法的时间复杂度是多少呢？ o(n)
过程
1 定义部分 1
2 输入部分 n
3 求解部分 n
4 输出部分 n
最后取最大值 n
提出方法3 思路 请思考用异或（位运算）
异或 一样为0，不一样为1
如果是9
9^0 结果是 9
9^9 结果是 0
|