algorithm - 这个算法的时间复杂度？ (大O)

Question

作为我作业的一部分，我正在尝试计算这段代码的时间复杂度。代码如下所示:

public int solvePuzzle( )
{
    searchAlg = BINARY_SEARCH ? new BinarySearch() : new LinearSearch();
    int matches = 0;
    for( int r = 0; r < rows; r++ )
        for( int c = 0; c < columns; c++ )
            for( int rd = -1; rd <= 1; rd++ )
                for( int cd = -1; cd <= 1; cd++ )
                    if( rd != 0 || cd != 0 )
                        matches += solveDirection( r, c, rd, cd );
    searchAlg.printStatistics();
    return matches;
}

此方法使用二进制搜索 或线性搜索。

我的作业要求我在 T(M,N) = O(?) 中找到它的时间复杂度，其中 M 是排序字典的大小，它将使用以下任一线性方式进行搜索二进制搜索，N 是“拼图”的大小 (char [][])，其中两个数组(行和列 = N = 相同大小)。

这部分匹配 += solveDirection( r, c, rd, cd ); 使用二进制/线性搜索来搜索排序数组。

到目前为止，这是我想出的。

二分查找的时间复杂度是Log M Linear Seach 的时间复杂度是 M

前两个for-loop的时间复杂度各为N。

但是第 3 和第 4 循环的时间复杂度是多少，T(M,N) 等于多少？

第 4 个循环的 3r 是 O(3) 吗？这是否意味着 T(M,N) = O(M * N * N * 3 * 3)/O(logM * N * N * 3 * 3)？

如有任何帮助，我们将不胜感激。

编辑:solveDirection() 的代码:

private int solveDirection( int baseRow, int baseCol, int rowDelta, int colDelta )
{
    String charSequence = "";
    int numMatches = 0;
    int searchResult;

    charSequence += theBoard[ baseRow ][ baseCol ];

    for( int i = baseRow + rowDelta, j = baseCol + colDelta;
             i >= 0 && j >= 0 && i < rows && j < columns;
             i += rowDelta, j += colDelta )
    {
        charSequence += theBoard[ i ][ j ];
        if ( charSequence.length() > maxWordLength )
            break;

        searchResult = searchAlg.search( theWords, charSequence );

        if( searchResult == theWords.length ) {   // corrected by UH 2007-05-02
            // either linear searched failed or binary search failed because charSequence
            // is larger than the largest word in theWords
            if ( searchAlg instanceof BinarySearch )
                break;    // binary search failed and it makes no sense to extend charSequence any further
            else
                continue; // linear search failed but an extension of charSequence may succeed
        }

        // precondition: 0 <= searchResult < theWords.length
        // At this point one, and only one, of three conditions holds:
        // 1. Linear search succeeded
        // 2. Binary search succeded
        // 3. Binary search failed at the insertion point for charSequence, 
        //    which means that theWords[ searchResult ] is the least element greater than charSequence

        if( PREFIX_TESTING && ! theWords[ searchResult ].startsWith( charSequence ) )
            break;

        if( theWords[ searchResult ].equals( charSequence ) ) {
//              if( theWords[ searchResult ].length( ) < 2 )
//                  continue;
            numMatches++;
            if ( PRINT_WORDS ) 
                System.out.println( "Found " + charSequence + " at " +
                        baseRow + " " + baseCol + " to " + i + " " + j );
        }
    }

    return numMatches;
}

Answer 1

你走在正确的轨道上。

然而，关键的见解是 O(k) = O(1) 对于任何常量 k(= 独立于输入的大小)。因此，您的 O(N·N·3·3) 与 O(N·N).这个结果需要与搜索相乘，你已经正确完成了搜索。