为什么当大小大于 50 时，该程序花费的时间会呈指数级增长？

所以我正在为类编写一个 ARM 汇编快速排序方法。我对大部分内容都有了解，除了复杂性没有意义。

我们将其与我们制作的另一种冒泡排序方法进行比较，它对于具有 1 个参数和 10 个参数的示例表现更好。然而，我什至无法比较 100 个参数测试，因为它需要太长时间......我什至无法让它完成 75 个参数测试，但 50 个参数测试在几秒钟内完成。

这就是我所拥有的，

qsort:  @ Takes three parameters:
    @   a:     Pointer to base of array a to be sorted (arrives in r0)
    @   n:  number of elements in the array (arrives in r1)

    stmfd   sp!, {r4, r6, lr}     @ Save r4 and r6 for caller
    mov     r6, r1                @ r6 <- right
    mov r2, #0                    @ r2 <- left
qsort_tailcall_entry:
    sub     r7, r6, r2            @ If right - left <= 1 (already sorted),
    cmp     r7, #1
    ldmlefd sp!, {r4, r6, pc}     @ Return, restoring r4 and r6
    ldr     r7, [r0, r2, asl #2]  @ r7 <- a[left], gets pivot element
    add     r1, r2, #1            @ l <- left + 1
    mov     r4, r6                @ r <- right
partition_loop:
    ldr     r3, [r0, r1, asl #2]  @ r3 <- a[l]
    cmp     r3, r7                @ If a[l] <= pivot_element,
    addle   r1, r1, #1            @ ... increment l, and
    ble     partition_test        @ ... continue to next iteration.
    sub     r4, r4, #1            @ Otherwise, decrement r,
    ldr     r8, [r0, r4, asl #2]  @ ... and swap a[l] and a[r].
    str     r8, [r0, r1, asl #2]
    str     r3, [r0, r4, asl #2]
partition_test:
    cmp     r1, r4                @ If l < r,
    blt     partition_loop        @ ... continue iterating.
partition_finish:
    sub     r1, r1, #1            @ Decrement l
    ldr     r3, [r0, r1, asl #2]  @ Swap a[l] and pivot
    str     r3, [r0, r2, asl #2]
    str     r7, [r0, r1, asl #2]
    bl      qsort                 @ Call self recursively on left part,
                                  @  with args a (r0), left (r2), r (r2),
                                  @  also preserves r4 and r6
    mov     r2, r4
    b       qsort_tailcall_entry  @ Tail-call self on right part,
                                  @  with args a (r0), l (r2), right (r6)

谁能帮助我理解为什么世界上它需要这么长时间并且呈指数级增长？我能做什么来解决它？

我没有研究你的逻辑，但在你的程序中添加了一些调试脚本，可能会对你有帮助。包装器是一个独立的程序。

/* qsort1.s */

@ ---- Added ----
.data

tstdat:
    .word 9, 9, 9, 9, 9

array:
    .word 3, 7, 8, 5, 2, 1, 9, 5, 4
len:
    .word ((len - array) /4)

.balign 4
format:
    .asciz " %2d  %2d  %2d  %2d  %2d  %2d  %2d  %2d  %2d  |  %2d  %2d  %2d\n"


.text

.global main

Print:
    push  {r0-v7, lr}
    mrs   v7,  cpsr
    push  {v7, v8}
    push  {r2, r6, r7}
    ldr   r7,  =array
    ldm   r7,  {r1-r9}
    push  {r4-r9}
    ldr   r0,  =format
    bl    printf
    add   sp,  #36
    pop   {v7, v8}
    msr   cpsr_f, v7
    pop   {r0-v7, pc}

main:

    ldr     r0,  =array
    ldr     r1,  =len
    ldr     r1,  [r1]

    push    {r3-r11, lr}
    bl      Print
    bl      qsort
    bl      Print
    pop     {r3-r11, pc}

@ ---------------------------

qsort:  @ Takes three parameters:
    @   a:     Pointer to base of array a to be sorted (arrives in r0)
    @   n:  number of elements in the array (arrives in r1)

    stmfd   sp!, {r4, r6, lr}     @ Save r4 and r6 for caller
    mov     r6, r1                @ r6 <- right
    mov     r2, #0                @ r2 <- left
qsort_tailcall_entry:
    sub     r7, r6, r2            @ If right - left <= 1 (already sorted),
@   bl      Print                @ <---- Added
    cmp     r7, #1
    ldmlefd sp!, {r4, r6, pc}     @ Return, restoring r4 and r6
    ldr     r7, [r0, r2, asl #2]  @ r7 <- a[left], gets pivot element
    add     r1, r2, #1            @ l <- left + 1
    mov     r4, r6                @ r <- right
partition_loop:
    ldr     r3, [r0, r1, asl #2]  @ r3 <- a[l]
    cmp     r3, r7                @ If a[l] <= pivot_element,
    addle   r1, r1, #1            @ ... increment l, and
    ble     partition_test        @ ... continue to next iteration.
    sub     r4, r4, #1            @ Otherwise, decrement r,
    ldr     r8, [r0, r4, asl #2]  @ ... and swap a[l] and a[r].
    str     r8, [r0, r1, asl #2]
    str     r3, [r0, r4, asl #2]
    bl      Print                @ <---- Added
partition_test:
    cmp     r1, r4                @ If l < r,
    blt     partition_loop        @ ... continue iterating.
partition_finish:
    sub     r1, r1, #1            @ Decrement l
    ldr     r3, [r0, r1, asl #2]  @ Swap a[l] and pivot
    str     r3, [r0, r2, asl #2]
    str     r7, [r0, r1, asl #2]
    bl      qsort                 @ Call self recursively on left part,
                                  @  with args a (r0), left (r2), r (r2),
                                  @  also preserves r4 and r6
    mov     r2, r4
    b       qsort_tailcall_entry  @ Tail-call self on right part,
                                  @  with args a (r0), l (r2), right (r6)

这是输出的开始。左边是要排序的数组，右边是r2、r6和r7。这个数组来自https://en.wikipedia.org/wiki/Quicksort https://en.wikipedia.org/wiki/Quicksort (https://upload.wikimedia.org/wikipedia/commons/a/af/Quicksort-diagram.svg https://upload.wikimedia.org/wikipedia/commons/a/af/Quicksort-diagram.svg).

pi@RPi:~/pgm $ mym qsort1
as -o qsort1.o qsort1.s
gcc -o qsort1 qsort1.o

./qsort1; echo $?
  3   7   8   5   2   1   9   5   4  |  2126935836  66296   0 (before pgm)
  3   4   8   5   2   1   9   5   7  |   0   9   3
  3   5   8   5   2   1   9   4   7  |   0   9   3
  3   9   8   5   2   1   5   4   7  |   0   9   3
  3   1   8   5   2   9   5   4   7  |   0   9   3
  3   1   2   5   8   9   5   4   7  |   0   9   3    
 ...
 (  array to be sorted             )    r2   r4  r7