程序和运行时间确定

Question

给出以下伪代码

D(A) // A is an array of numbers
U_Size = 1
for i=2 to length(A)
   U=?
   for j=1 to U_Size
      if A[j]=A[i]
        then U = FALSE
            j = U_size
   if U = TRUE
     then U_Size = U_Size + 1
        A[U_Size]=A[i]
return U_Size

替换“?”的最佳选项是什么？在第 4 行？ ( U=? )
这个程序到底做了什么 - Answered
我应该如何确定此程序的运行时间和 space 复杂度

MY ANSWER: In line 4, I initialized U -> U = TRUE and figured that the program arranges all of the different elements of the array in the beginning of the arry and returns the amount of different elements
The Question remained unanswered is: How should I determine the run-time & space complexity of this program (2)

Answer 1

如果您不熟悉 Big O notation，我建议您阅读它，因为在计算机科学中我们用它来表示时间和 space 复杂性。

令输入数组的长度为n。
这段代码的时间复杂度在最坏情况下为 O(n²) 并且最坏情况发生在所有不同的数组中数字。对于所有不同数字的输入数组，if 条件 if A[j] = A[i] 始终为假，因此 j 的内部循环对于每个 i 从 1 循环到 U_size ] 并且 U_size 每次都会增加 1。
如果仍然不清楚，那么您可以使用数学对所有不同数字的数组进行理解。

对于i = 2和U_size = 1，j的内循环从1 to 1开始运行，即1次。
对于i = 3和U_size = 2，j的内循环从1 to 2开始运行，即2次。
对于i = 4和U_size = 3，j的内循环从1 to 3开始运行，即3次。
对于i = 5和U_size = 4，j的内循环从1 to 4开始运行，即4次。
.
.
.
.
.
对于i = n (length of array A)和U_size = n-1，j的内循环从1 to n-1开始运行，即n-1次。

因此，如果您对 i 的所有迭代求和运行次，
1 + 2 + 3 + 4 + ... + n-1，你得到 n*(n-1)/2 ~ O(n²).

现在，space 复杂性。您已经使用数组 A 本身在 j 循环之后进行赋值。如果您不考虑用于报告 space 的输入数组，那么您会得到 O(1) 作为 space 复杂度。

如果您存储一个单独的数组来分配元素，即 A[U_Size]=A[i] 或者您认为输入数组本身用于 space，那么您会说 space 复杂度为 O(n).

程序和运行时间确定

Program and run time determination

algorithm

data-structures

runtime

pseudocode