依赖于 2 个输入的算法的时间复杂度 T(n)

Question

通常在分析算法的运行时间时，我正在处理影响运行时间的单个输入。我试图了解当有 2 个或更多输入影响运行时间时如何表示 T(n)。

例如在最坏情况下的线性搜索：

function LinearSearch(arr, N, x)
    for (i = 0; i < N; i++)        ---> C1*N + C2
        if arr[i] = x              ---> C3*N
            return true            

    return false                   ---> C4

T(n) = (C1 + C3)*N + (C2 + C4) =CN+C

所以 T(n) 关于 N 是线性的。

现在假设有另一种算法接受输入 X 和 Y，我做了类似的分析，发现最坏情况下的成本是：

T(n) = CX + C

最好的情况是：

T(n) = CY + C

我的问题是，这样表示运行时间是否正确？鉴于在不同情况下有两种不同的输入会影响运行时间。

我在网上和教科书上都没有找到太多信息，但我一直在思考T(n)中的n是否代表所有输入，或者可以这样表示：

T(X) = CX + C

T(Y) = CY + C

我还在一篇研究论文中看到了一种算法，其描述类似于：

T(n, m) = 一些表达式

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

谢谢

编辑：时间复杂度取决于两个输入的算法示例可以是基数排序。

据我所知，基数排序通常表示为 O(n*k)，其中 n 是要排序的元素数，k 是最大值的位数。

忽略 T(n) 的确切细节，这将如何表示？

Answer 1

如果算法的复杂度取决于单个参数，而您想调用该参数 X，则时间复杂度也将取决于 X 而不是 n （什么是 n？）：例如T(X) = X^2.

如果算法的复杂度取决于参数n1, n2, ..., nk（且参数相互独立），则时间复杂度为k 参数中的一个函数，T(n1, ..., nk).

例如，采用长度为 x 和 y 的两个字符串并打印它们的算法的时间复杂度为 T(x,y) = O(x + y)。

依赖于 2 个输入的算法的时间复杂度 T(n)

Time complexity T(n) for an algorithm that depends on 2 inputs

algorithm

time-complexity

analysis