这个算法的时间复杂度？（大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;
}

此方法使用 Binary Search 或 Linear Search。

我的作业要求我在 T(M,N) = O(?) 中找到它的时间复杂度，其中 M 是排序字典的大小，它将使用线性搜索或二进制搜索进行搜索，N 是 "puzzle" (char [][]) 其中两个数组（行和列 = N = 相同大小）。

这部分 matches += solveDirection( r, c, rd, cd ); 使用 binary/linear 搜索来搜索排序数组。

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

二分查找的时间复杂度是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)。这个结果需要乘以搜索，你做对了。

这个算法的时间复杂度？（大O）

Time complexity of this algorithm? (Big O)

algorithm

performance

big-o

这个算法的时间复杂度？ （大O）

Time complexity of this algorithm? (Big O)

algorithm

performance

big-o

这个算法的时间复杂度？（大O）