该函数对 Big O 的内存要求是多少?
渐进运行时间为 O(n)。不知道如何获得大 O 表示法中的“内存需求”。
<?php
$numbers = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450';
$length_given = 1000;//no need to use strlen()
$highest = 0;
$running_total = 1;
$first_digit = $numbers[0];//better than checking on iteration if $i==0
$seq=0;//start of sequence
for($i = 0; $i< $length_given; $i++)
{
$current_digit = (int) $numbers[$i]; //converting to int as precaution
if($current_digit == 0)//zero found
{
if($i==$length_given-1)
{
break;//don't bother doing anymore if last digit is zero
}
//reset sequence/digit counter & total and skip this digit
$seq = 0;
$running_total=1;
}
else//non-zero
{
/*update running total:
* divide running total by the previous product (to remove it from total)
* and multiple in the new product but if sequence is initializing
* (at start or after zero found) then just multiple in product (use 1 as divisor)
*/
$running_total = ($running_total/ ($seq<=4? 1 : $numbers[$i-5]) ) * $current_digit;
if($running_total>$highest)
{
/* Always true when sequence is started/restarted after zero found because
* the running total can't go down because the products will be greater than zero*/
$highest = $running_total;
}
$seq++;
}
}
echo $highest;
?>
Asymptotic Run-time is O(n). Not sure how to get "memory requirements" in Big O notation.
<?php
$numbers = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450';
$length_given = 1000;//no need to use strlen()
$highest = 0;
$running_total = 1;
$first_digit = $numbers[0];//better than checking on iteration if $i==0
$seq=0;//start of sequence
for($i = 0; $i< $length_given; $i++)
{
$current_digit = (int) $numbers[$i]; //converting to int as precaution
if($current_digit == 0)//zero found
{
if($i==$length_given-1)
{
break;//don't bother doing anymore if last digit is zero
}
//reset sequence/digit counter & total and skip this digit
$seq = 0;
$running_total=1;
}
else//non-zero
{
/*update running total:
* divide running total by the previous product (to remove it from total)
* and multiple in the new product but if sequence is initializing
* (at start or after zero found) then just multiple in product (use 1 as divisor)
*/
$running_total = ($running_total/ ($seq<=4? 1 : $numbers[$i-5]) ) * $current_digit;
if($running_total>$highest)
{
/* Always true when sequence is started/restarted after zero found because
* the running total can't go down because the products will be greater than zero*/
$highest = $running_total;
}
$seq++;
}
}
echo $highest;
?>
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
内存需求捕获除了输入数据之外还需要的内存量。在您的情况下,您只保存一些变量,当输入变大时,这些变量的大小不会改变,因此内存/空间是固定的并且 O(1) 。
Memory requirements captures the amount of memory needed in addition to the input data. In your case you only hold a few variables whose size does not change when the input grows larger so memory/space is fixed and O(1).