Euler Project 14-PHP中最长的排序规则序列

Question

这是我对Euler Project Problem 14 的解决方案

<?php
$count = 0 ;
$max = 0;
for($n = 2 ; $n < 1000000 ; $n++){
        while ($n > 1)
        {
            if ($n % 2 == 0 )
            {
                $n = $n/2;
            }
            else
            {
                $n = 3*$n + 1 ;
            }               
            $count += 1;
           if($count > $max )
           {
                $max = $count;
                $final = $n;    
           }
        }
     }
     echo $final;
>?

跑了这么长时间。我查看了其他一些解决方案，它们在逻辑上与我的代码非常相似，但运行速度比我的快得多。我的问题是，是什么让我的代码效率低下？我在这里错过了什么？

谢谢^^

Answer 1

您的方法直截了当且未经打磨。

您可以使用动态编程来改进运行时（复杂性方法）。

假设你想计算5。您将拥有：5->16->8->4->2->1。但是，如果您这样做，您还将计算出8和16的值。这个想法是存储您已经计算出的值，以便在以后需要时保存工作。

研究算法的复杂性将是一些问题的关键，所以最好尽早习惯它。

它慢的另一个原因是语言的选择。例如，尝试使用C，它会运行得更快。