彙編代碼的時間複雜度分析

編輯：
該程序集實現了算法的時間複雜度？彙編代碼的時間複雜度分析

.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

謝謝！

來源

2011-04-30 Agnius Vasiliauskas

你明白什麼時間複雜性意味着什麼？ – 2011-04-30 18:48:39

投機性地添加了[作業]標籤。 – 2011-04-30 18:51:06

不，這不是家庭作業，它只是ASM和CS大師們的有趣難題... – 2011-05-01 09:51:21

這裏只有你組裝的一小部分，在那裏比直行執行或向前跳躍等方式控制流（或調用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）中。

來源

2011-05-04 23:40:51

非常好，謝謝！ – 2011-05-05 07:42:58

時間複雜度與算法有關，而不是實現，因此您必須「反向工程」回去。

你必須用每種語言來完成它，程序集就是其中之一。

理解使用 - say - java表達的算法比使用ASM更簡單的事實並不會改變事態。

編輯：這個答案的部分只是從我的意見下面複製。

來源

2011-04-30 18:48:36 akappa

首先，您需要將x86代碼「逆向工程」回到更高層次的抽象，例如，僞代碼，然後對其進行分析。 – 2011-04-30 18:57:38

@ 0x69：您必須瞭解算法在每種語言中的含義，程序集就是其中之一。使用 - say - java理解算法更容易的事實並不能改變事態。 – akappa 2011-04-30 19:13:51

沒有必要對任何東西進行「逆向工程」。彙編對於算法來說是一個非常好的明確的描述語言，與僞代碼沒有區別。您可以對原始裝配源執行完全相同的分析以確定時間或空間複雜性。 – 2011-04-30 19:16:30

彙編代碼的時間複雜度分析

回答

相關問題