小编Let*_*eta的帖子

有人可以帮我理解https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html中给出的汇编程序

它是这样的:

uint64_t msr;
asm volatile ( "rdtsc\n\t"    // Returns the time in EDX:EAX.
               "shl $32, %%rdx\n\t"  // Shift the upper bits left.
               "or %%rdx, %0"        // 'Or' in the lower bits.
               : "=a" (msr)
               :
               : "rdx");

它与以下内容有何不同:

uint64_t msr;
asm volatile ( "rdtsc\n\t"
               : "=a" (msr));

为什么我们需要转移和/或操作以及rdx到底有什么作用？

编辑:添加了原始问题尚不清楚的内容.

• 什么"\n\t"做什么？
• ":"做什么？
  • 分隔符输出/输入/ clobbers ...
• rdx末尾是否等于0？

回顾一下.第一行加载寄存器eax和edx中的时间戳.第二行将eax中的值移位并存储在rdx中.第三行将edx中的值与rdx中的值一起使用,并将其保存在rdx中.第四行将rdx中的值赋给我的变量.最后一行将rdx设置为0.

• 为什么前三行没有":"？
  • 他们是一个模板.输出带有":"的第一行,第二行是可选输入,第三行是clobbers的可选列表(已更改的寄存器).
• 实际上是eax和d - edx吗？这是硬编码的吗？

再次感谢!:)

EDIT2:回答了我的一些问题......

根据Wikibooks，如果所有点都已排序，则安德鲁算法以线性时间运行。我们将采用排序点的情况。

但是，在伪代码中它说：

for i = 1, 2, ..., n:
while L contains at least two points and the sequence of last two points
        of L and the point P[i] does not make a counter-clockwise turn:
    remove the last point from L
append P[i] to L

现在，在这里我们可以看到 for 循环和嵌套在 for 循环内的 while 循环。根据我的逻辑推理，如果循环内部有循环，它根本不可能具有线性时间复杂度。

我在哪里犯了错误？谢谢！

编辑：通过分析代码，我推断出以下内容。

for i loop--------O(n)
    while loop----O(i-2) worst case
        remove----O(1)
    append--------O(1)

现在，如果 while 循环的时间复杂度为 O(n)，则整体复杂度将为 O(n^2)。但是因为它更小，所以整体复杂度应该是 O((i-2) * n)，我认为它比 O(n) 大，因为 i 增加到 n...

我不太确定如何正确计算这个......