芯片测试算法及时间复杂度分析
芯片测试算法及时间复杂度分析
·
一.蛮力算法与分治算法
#include <stdio.h>
#include <math.h>
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int Status;
//芯片测试蛮力算法
void ChipTest_1()
{
printf("请输入芯片个数\n");
int amount;
scanf("%d", &amount);
getchar();
//一片一片测试,好芯片需要测试芯片中至少一半证明它是好芯片,坏芯片需要测试芯片中多于一半证明
//它是坏芯片
//前提是好芯片至少比坏芯片多一片
int count, test_ceil_amount;
for (int i = 1; i <= (int)ceil((double)amount / 2); i++)
{
count = 0;
for (int j = i + 1; j <= amount; j++)
{
printf("请输入第%d块芯片测试第%d块芯片的结果,用“T”与“F”表示\n",j,i);
char c = getchar();
getchar();
if (c == 'T')
count++;
}
test_ceil_amount = amount - i;
if (count >= (int)ceil((double)test_ceil_amount / 2))
{
printf("第%d片是好芯片\n", i);
break;
}
else
printf("第%d片是坏芯片\n", i);
}
}
//芯片测试分治算法
Status ChipTest_2(int amount)
{
if (amount == 1)
{
printf("剩余芯片一定为好芯片\n");
return OK;
}
//如果芯片总数为奇数则会有轮空芯片产生,其余芯片测试这个轮空芯片,如果为好芯片,测试成功,坏
//芯片则淘汰
if (amount % 2 == 1)
{
int count = 0;
for (int i = 1; i <= amount - 1; i++)
{
printf("请输入第%d块芯片测试第%d块芯片的结果,用“T”与“F”表示\n", i, amount);
char c = getchar();
getchar();
if (c == 'T')
count++;
}
if (count >= (int)ceil(((double)amount - 1) / 2))
{
printf("第%d片是好芯片\n", amount);
return OK;
}
else
{
printf("第%d片是坏芯片\n", amount);
amount--;
}
}
//芯片总数一定为偶数,可以取两片芯片相互测试,如果都报好,取一片留一片,一好一坏或者测试结果
//都为坏都扔掉
//这样留下的每个组的情况只可能是都好或者都坏,其他两种情况都扔掉是因为这样一组至少可以排除一
//个坏芯片,仍然保持好芯片数量比坏芯片多
int chipcount = amount;
for (int i = 1; i <= amount / 2; i++)
{
printf("请输入第%d块芯片测试第%d块芯片的结果,用“T”与“F”表示\n", 2 * i - 1, 2 * i);
char c1 = getchar();
getchar();
printf("请输入第%d块芯片测试第%d块芯片的结果,用“T”与“F”表示\n", 2 * i, 2 * i - 1);
char c2 = getchar();
getchar();
if (c1 == 'T' && c2 == 'T')
{
printf("取一片扔一片\n");
chipcount--;
}
else
{
printf("都扔\n");
chipcount -= 2;
}
}
ChipTest_2(chipcount);
}
int main()
{
int amount = 5;
ChipTest_2(amount);
}
二.时间复杂度分析
1.分治算法
W(n)=W(n/2)+O(n),W(1)=0
等式右边第一项至多n/2规模,因为可能芯片会全扔,O(n)为轮空处理,n为奇数时候进行处理,偶数时候不需要,经过迭代得出W(n)=O(n),为线性时间复杂度。
2.蛮力算法
W(n)=W(n-1)+n-1,W(n/2)=0
好芯片比坏芯片多一片,测试剩余n/2还没找到好芯片说明剩余芯片都为好芯片,经过迭代可知W(n)=O(n^2),所以分治算法比蛮力算法好。

DAMO开发者矩阵,由阿里巴巴达摩院和中国互联网协会联合发起,致力于探讨最前沿的技术趋势与应用成果,搭建高质量的交流与分享平台,推动技术创新与产业应用链接,围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
所有评论(0)