这个程序的时间复杂度是多少？

Question

好的！！这不是作业！我的问题是 "Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring." 常规方法是 O(n * n) 并且通过使用动态编程我得到了一种与以下程序非常相似的更好方法。据我所知， O(n) 和 O(2n) 可以被认为是相同的。所以 O(n * n/2) 仍然等同于 O(n*n)？

代码如下：

for(int i =0; i < n; i++)
{
  for(int j = 0; j< i; j++)
  {
    if (array[i][j] != 0)
    array[i][j] = -1;
  }
}

Answer 1

虽然老实说这看起来像是一道家庭作业题，但我还是要回答它，希望我能在整个过程中帮助解释它：

首先，您有一个嵌套循环。通常，如果每个循环的最大值与 n.

相关，则嵌套循环通常具有 O(n²) 的时间复杂度

对于您的情况，我会将其分解为视觉表示，希望它有意义：

想象一个宽度和高度为 n 的正方形（first/outer 循环的最大值）。对于这种情况，我会选择 n = 5:

o  o  o  o  o  
o  o  o  o  o  
o  o  o  o  o  
o  o  o  o  o  
o  o  o  o  o

现在，有了这个方块，您可以将每一行想象成 i 的一次迭代，而每一列将代表您的 j 索引和您达到的距离。当我们标记将在我们的算法中访问的 table 中的哪些 o 时，我们将看到一个整洁的模式。

如果您自己逐步完成，完成后您会看到以下结果：

o  o  o  o  o  
x  o  o  o  o  
x  x  o  o  o  
x  x  x  o  o  
x  x  x  x  o

从这里我们可以看到大约一半的广场已经被访问。由于我们知道广场的面积为 n²，因此我们可以说我们访问了广场的 n²/2 部分。因此，运行时间也是 O(n²/2) 然后减少到 O(n²) 因为系数可以被忽略。

这个程序的时间复杂度是多少？

What's the time complexity of this program?

algorithm

time-complexity