我的gcc版本是4.8.2,操作系统是ubuntu 14.04(64位).我发现有时gcc自动生成金丝雀有时候不做缓冲区溢出保护,为什么？
生成金丝雀的情况:当SIZE是四的倍数时
#include<stdio.h>
#define SIZE 4
int main()
{
char s[SIZE];
scanf("%s", s);
return 0;
}
asm在gcc -c -g -Wa,-a,-ad之后
...
4:a.c **** int main()
5:a.c **** {
13 .loc 1 5 0
14 .cfi_startproc
15 0000 55 pushq %rbp
16 .cfi_def_cfa_offset 16
17 .cfi_offset 6, -16
18 0001 4889E5 movq %rsp, %rbp
19 .cfi_def_cfa_register 6
20 0004 4883EC10 subq $16, %rsp
21 .loc 1 5 0
22 0008 64488B04 movq %fs:40, %rax
22 25280000
22 00
23 0011 …这不是功课,我正在研究摊销分析.有些事让我感到困惑.我无法完全理解摊销和平均复杂性之间的含义.不确定这是对的.这是一个问题:
-
我们知道程序的运行时复杂性取决于程序输入组合---假设具有运行时复杂度O(n)的程序的概率是p,其中p << 1,在其他情况下(即对于(1) -p)可能的情况),运行时复杂度为O(logn).如果我们使用K个不同的输入组合运行程序,其中K是一个非常大的数字,我们可以说这个程序的摊销和平均运行时复杂度是:
-
第一个问题是:我在这里读到了这个问题:平均案例和摊销分析之间的差异
所以,我认为平均运行时复杂性没有答案.因为我们不知道平均投入是多少.但似乎是p*O(n)+(1-p)*O(logn).哪个是正确的,为什么？
第二,摊销部分.我读过Constant Amortized Time,我们已经知道Amortized分析与平均案例分析的不同之处在于概率不涉及; 摊销分析保证了最坏情况下每项操作的平均表现.
我可以说,分摊的运行时间是O(n).但答案是O(p n).我有点混淆为什么涉及概率.虽然O(n)= O(p n),但我真的不知道为什么p会出现在那里？我改变了思维方式.假设我们丢失了很多次,那么K变得非常大,因此摊销的运行时间是(K p O(n)+ K*(1-p)O(logn))/ k = O(p n).它似乎与平均情况相同.
对不起,请帮帮我,先谢谢!