由[交换两个变量的值问题]理解程序的时空复杂度

rgw2

由一个编程经典问题，交换两个变量的值入手，理解程序的时空复杂度（以下均使用PHP代码演示问题的解决方法）
解决问题的方法一：
    1.方法文字描述：使用一个中间变量temp，实现两个变量值的互换
    2.实现的具体代码：

1 2 3 4 5 6 7 8 9 10 11 12

<?php //声明两个变量$a，$b $a = $_GET['a'];   $b = $_GET['b']; //打印没有互换前，$a和$b var_dump("未替换前：a={$a} and b={$b}"); //使用中间变量$temp实现$a和$b互换 $temp = $a; $a = $b; $b = $temp; var_dump("使用temp中间变量替换后：a={$a} and b={$b}"); ?>

     3.此时时空复杂度
        时间复杂度即程序运算次数，3次赋值运算
        空间复杂度即占用内存大小，除了原本的$a和$b两个变量，增加了$temp中间变量，所以空间复杂度为3（具体是3个字符串）

为了降低内存使用量，避免使用中间变量的实现方式，使用异或运算符实现
解决问题的方法二：
    1.方法文字描述：使用异或运算符
    2.实现的具体代码：

1 2 3 4 5 6 7 8 9 10 11 12

<?php //声明两个变量$a，$b $a = $_GET['a'];   $b = $_GET['b']; //打印没有互换前，$a和$b var_dump("未替换前：a={$a} and b={$b}"); //使用异或运算实现$a和$b互换 $a = $a ^ $b; $b = $a ^ $b; $a = $a ^ $b; var_dump("使用异或运算符替换后：a={$a} and b={$b}")； ?>

    3.此时的时空复杂度
        时间，3次赋值运算，3次异或运算，6次
        空间，只使用原本的2个变量，$a和$b，空间复杂度为2
注意：在PHP中得异或操作，前面的字符串的长度要大于等于后面的字符串，因为，比如'abc' ^ 'defgh'，PHP就只会执行'abc' ^ 'def'。gh会被省略