Анализ сложности времени сборки кода - PullRequest
Новая
       4

Анализ сложности времени сборки кода

1 голос
/ 30 апреля 2011

РЕДАКТИРОВАТЬ:
Во сколько сложность времени алгоритм реализован в этой сборке? 

    .file   "a.c"
    .section    .rodata
.LC0:
    .string "%d\n"
.LC1:
    .string "%d"
    .text
.globl main
    .type   main, @function
main:
    pushl   %ebp
    movl    %esp, %ebp
    andl    $-16, %esp
    subl    $32, %esp
    cmpl    $1, 8(%ebp)
    jg  .L2
    movl    $.LC0, %eax
    movl    $-1, 4(%esp)
    movl    %eax, (%esp)
    call    printf
    jmp .L8
.L2:
    movl    $.LC1, %edx
    movl    12(%ebp), %eax
    addl    $4, %eax
    movl    (%eax), %eax
    leal    24(%esp), %ecx
    movl    %ecx, 8(%esp)
    movl    %edx, 4(%esp)
    movl    %eax, (%esp)
    call    __isoc99_sscanf
    testl   %eax, %eax
    jne .L4
    movl    $.LC0, %eax
    movl    $-2, 4(%esp)
    movl    %eax, (%esp)
    call    printf
    jmp .L8
.L4:
    movl    24(%esp), %eax
    testl   %eax, %eax
    jns .L5
    movl    $.LC0, %eax
    movl    $-3, 4(%esp)
    movl    %eax, (%esp)
    call    printf
    jmp .L8
.L5:
    movl    $0, 28(%esp)
    jmp .L6
.L7:
    addl    $1, 28(%esp)
.L6:
    movl    24(%esp), %eax
    cmpl    %eax, 28(%esp)
    jl  .L7
    movl    $.LC0, %eax
    movl    28(%esp), %edx
    movl    %edx, 4(%esp)
    movl    %eax, (%esp)
    call    printf
.L8:
    leave
    ret
    .size   main, .-main
    .ident  "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
    .section    .note.GNU-stack,"",@progbits

Спасибо!

Ответы [ 2 ]

2 голосов
/ 05 мая 2011

Существует только небольшая часть вашей сборки, в которой управление передается иначе, чем прямолинейное выполнение или переходы вперед (или вызовы printf или sscanf со строкой формата "%d"). Поскольку эти разделы кода выполняются только один раз, они имеют сложность O (1).

Таким образом, единственная интересная сложность заключается в том месте, где возможен прыжок назад: 

.L5: movl    $0,    28(%esp)
     jmp     .L6
.L7: addl    $1,    28(%esp)
.L6: movl 24(%esp),    %eax
     cmpl    %eax,  28(%esp)
     jl      .L7

Это просто базовый цикл; в C это будет выглядеть так: 

for (int i=0; i<n; ++i);

В сторону: возникает опасность использования «абстрактного псевдокода» для обсуждения сложности сборки; этот цикл ничего не делает, поэтому абстрактный эквивалент псевдокода в некотором смысле пуст и имеет сложность O (1). Реальный код, однако, имеет сложность O (n).

Таким образом, этот цикл занимает время O (n), где n - это значение ввода в программу в виде целого числа. Поскольку остальная часть программы занимает O (1) времени, программа в целом выполняется за O (n).

2 голосов
/ 30 апреля 2011

Сложность по времени связана с алгоритмом, а не с реализацией, поэтому вам придется «перепроектировать» его обратно.

Вы должны делать это с каждым языком, ассемблер - только один из них.

Тот факт, что понимание алгоритма, выраженного с помощью, скажем, Java, проще, чем с помощью ASM, не меняет положения дел.

Редактировать: части этого ответа просто скопированы из моих комментариев ниже.

...