线性搜索算法优化

Question

我刚刚完成了计算机科学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;
}

Answer 1

它或多或少存在,但并不完全.在大多数情况下,它是O(n),但如果每个ticketNum都大于每个winsNum,则为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个.这与您的算法具有几乎相同的行为,但更容易理解,更容易看出它是正确的.

Answer 2

你基本上是在寻找两组交集的大小.鉴于大多数lottos使用大约50个球(左右),您可以将数字存储为以无符号长整数设置的位.找到共同的数字就是将两者结合起来的简单问题:commonNums = TicketNums & winningNums;.

找到交集的大小是计算结果数中的一位的问题,这是先前已经涵盖的主题(尽管在这种情况下,您使用的是64位数字,或者是一对32位数字,而不是一个32位数字).