-1

我试图在下面找到算法的最坏情况复杂性。该算法在具有 n > 1 个元素的数组 DATA 中找到最大元素的位置 LOC1 和第二大元素的位置 LOC2。我将复杂性作为算法执行期间比较的数量，

FIND(DATA, N, LOC1, LOC2)

    1. Set FIRST = DATA[1], SECOND = DATA[2], LOC = 1, LOC2 = 2.

    2. IF FIRST < SECOND then:
    a. Interchange FIRST and SECOND.
    b. Set LOC1 = 2 and LOC2 = 1.
    [End of If structure.]

    3. Repeat for  K= 3 to N:
    If FIRST < DATA[K], then:
    a. Set SECOND = FIRST and FIRST = DATA[k].
    b. Set LOC2 = LOC1 and LOC2 = K.
    Else if SECOND < DATA[K], then:
        Set SECOND = DATA[K] and LOC2 = K.

    [End of loop.]

    4. Return

我无法弄清楚如何找到上述程序的复杂性，因为比较的数量将取决于数组中元素的排列方式。对于最坏的情况，将 SECOND 元素与 DATA[K] 进行比较的 else 条件也应执行最大次数。但是根据 DATA 数组的元素，可能会有很多情况。

谢谢，

问候

tek3

4

1 回答 1

1

最坏的情况是第 3 步总是对所有 n-2 次迭代执行两次比较。因此，第 2 步有一次比较，第 3 步有 2*(n-2) 次比较。

于 2013-04-03T18:16:53.287 回答