线性搜索算法优化
我刚刚完成了计算机科学1的作业问题（是的，这是作业，但听我说！）。 现在，这个任务已经完成并且工作了，所以我不需要帮助。 我的问题涉及到我使用的算法的效率（我们没有对算法效率进行评分，我只是很好奇）。
我要介绍的功能目前使用线性搜索算法的修改版本（我自己想出了这个算法！），以便检查给定彩票上的数字与获胜的数字相匹配，假设两者都是票上的号码和所画的号码按升序排列。 我想知道，有什么方法可以使这个算法更有效率吗？
/*
* Function: ticketCheck
*
* @param struct ticket
* @param array winningNums[6]
*
* Takes in a ticket, counts how many numbers
* in the ticket match, and returns the number
* of matches.
*
* Uses a modified linear search algorithm,
* in which the index of the successor to the
* last matched number is used as the index of
* the first number tested for the next ticket value.
*
* @return int numMatches
*/
int ticketCheck( struct ticket ticket, int winningNums[6] )
{
int numMatches = 0;
int offset = 0;
int i;
int j;
for( i = 0; i < 6; i++ )
{
for( j = 0 + offset; j < 6; j++ )
{
if( ticket.ticketNum[i] == winningNums[j] )
{
numMatches++;
offset = j + 1;
break;
}
if( ticket.ticketNum[i] < winningNums[j] )
{
i++;
j--;
continue;
}
}
}
return numMatches;
}
这或多或少，但不完全。 在大多数情况下，它是O（n），但如果每个ticketNum大于每个获胜数，则它是O（n ^ 2）。 （这是因为内j循环不break时j==6像它应该，但在下次运行i迭代来代替。）
你希望你的算法在每一步增加i或j ，并在i==6或j==6时终止。 [如上所述，你的算法几乎可以满足这个要求。]结果，你只需要一个循环：
for (i=0,j=0; i<6 && j<6; /* no increment step here */) {
if (ticketNum[i] == winningNum[j]) {
numMatches++;
i++;
j++;
}
else if (ticketNum[i] < winningNum[j]) {
/* ticketNum[i] won't match any winningNum, discard it */
i++;
}
else { /* ticketNum[i] > winningNum[j] */
/* discard winningNum[j] similarly */
j++;
}
}
显然这是O（n）; 在每个阶段，它或者增加i或者j ，所以它能够做的最多的步骤是2 * n-1。 这与您的算法具有几乎相同的行为，但更容易遵循，并且更容易看出它是正确的。
你基本上是在寻找两个交集的大小。 考虑到大多数热靴使用大约50个球（或者大约50个球），您可以将数字存储为以无符号长整数设置的比特。 然后找出常见数字是一个简单的问题，将两者结合在一起： commonNums = TicketNums & winningNums; 。
查找交集的大小是计算结果数字中的一位数的问题，前面已经介绍了一个主题（尽管在这种情况下，您将使用64位数字或一对32位数字）的一个32位数字）。
是的，有更快的速度，但可能会使用更多的内存。 在可能的数字大小中使数组满量程0，在每个绘制的数字上放置一个1。 对于每个门票号码，在该号码的索引处添加该值。
int NumsArray[MAX_NUMBER+1];
memset(NumsArray, 0, sizeof NumsArray);
for( i = 0; i < 6; i++ )
NumsArray[winningNums[i]] = 1;
for( i = 0; i < 6; i++ )
numMatches += NumsArray[ticket.ticketNum[i]];
12轮循环而不是36循环周围的代码留作练习。
编辑：它也有不需要对两组值进行排序的优点。
链接地址: http://www.djcxy.com/p/36349.html