这个伪代码的时间复杂度是多少？

Question

我没有很多计算复杂性的知识。你能帮忙估计一下下面伪代码的复杂度吗？

算法一：

Input: V1, V2 and V3 and another vector C// Vectors of size n
Output: response..
V_f = f(V1, V2, 3) // function performs simple multiplication and additions on the vector
for i in range(0,n) // loop over element in the vector
     if V_f(i) != C(i) 
              // sort the V1(i), V2(i) and V3(i) and retrieve the middle value
              // if the middle value is in a range of certain values then launch Algorithm 2  
             // Over the result of Algorithm 2 (using if expressions), print the response
// end and return result

算法 2

Input: Sorted

 Values C{1}, C{2} and C{3} and the vector C

Output: Response:

for i in range (o,n) // loop over the elements 
       // According to the values of C and C{i}, perform additions (using if expressions)
// end and return result

循环内的操作只是加法或简单的测试。此外，算法 2 是使用算法 1 执行的，这意味着我在循环中有一个循环（对吗？）：

for i in range (n)
// operations
// for j in range (n)
// operations

那么这是否意味着这个算法的时间复杂度是O(n^2)？其中 n 是矢量的大小？

同样是一个一般性的问题，如果算法1和算法2并行执行，整体复杂度是多少？是每个算法复杂度的总和还是最大值？

Answer 1

算法1

算法1首先对向量进行简单的乘法和加法运算。假设它在每个向量上从头到尾循环并执行一些计算，则进行的迭代次数将为 3*N ，这将被视为 O(N)
```
V_f = f(V1, V2, 3)          #Time complexity will be O(N)
```
第一个算法中的下一条语句也将从0 to N开始循环。假设在每种情况下 V_f(i) != C(i) ，您都必须对 V1[i]、V2[i]、V3[i] 进行排序，这将花费常数 O(1) 时间。
```
for i in range(0,n) // loop over element in the vector
    if V_f(i) != C(i) 
```
在下一条语句中，您要检查的是上述排序元素的中间值是否在特定范围内 - // if the middle value is in a range of certain values then launch Algorithm 2 ，现在时间复杂度取决于检查的方式和大小范围是。我假设您需要检查从 a 到 b 的连续范围，因此这一步将只需要 O(1)。现在将调用 Algorithm2。

算法2

算法 2 -

 for i in range (o,n) // loop over the elements 
        // According to the values of C and C{i}, perform additions (using if expressions)
 // end and return result

在这里，您将再次从 0 to N 循环并在每次迭代中执行一些计算，这将花费 O(1)。因此整个算法的总时间复杂度为 O(N)2。

So does this mean the time complexity of this algorithm is O(n^2)?

现在，假设最坏情况，您将不得不运行算法 2 algorthm1 循环内的每次迭代。因此，如您所说，时间复杂度为 O(N^2)。请注意，这也将取决于计算的简单程度，如何完成对特定值范围的检查，以及对我们最终时间复杂度的常数的贡献。但假设它们不超过 O(N)，您的总体时间复杂度将是 O(N^2)

这个伪代码的时间复杂度是多少？

What is the time complexity of this peudo code?

algorithm

performance

pseudocode

time-complexity

算法1

算法2