减少Perl阵列的时间复杂度

Question

我有一个阵列

[3, 1, 2, 5, 4, 6]

我想将其排序(更改sort为arranging in a certain pattern)为:向右移动并将索引替换为右侧的下一个最高整数.说在这个数组中3被替换为5,1被替换为2等等.

我希望输出为

[5, 2, 5, 6, 6, 6]

算法:

1. 启动一个forloop.它会迭代到最后一个元素
2. 从第一个索引开始,它将与下一个索引匹配并比较该值
3. 如果第二个索引小于第一个,则转到第三个索引
4. 如果不是用第二个索引更改第一个索引
5. 尝试使用所有索引

这是一种常规算法.但时间复杂度是n*n.(不完全是n*n).

有没有办法降低复杂性.因为在大型阵列的情况下,它会非常慢.有人可以为我提供时间复杂度的算法n.

添加代码

use strict;
use warnings;

my @arr1 = qw/3 1 2 5 4 6/;
my @arr2;
my ($j, $i);
for($i = 0; $i <= $#arr1; $i++) {
    $j = $i;
    while ( $j < $#arr1) {
        if ( $arr1[$i] < $arr1[$j+1]) {
            push @arr2,$arr1[$j+1];
            last;
        } 
        if ($i == $#arr1) {
            push @arr2,$arr1[$j];
        }
        $j++;
    }

}
push @arr2, $arr1[$#arr1];   ## Pushing the last array index

print @arr2;

输出:

525666

Answer 1

您当前的算法可以多次触摸一个位置,这是低效的.通过递归的力量,我们可以做得更好.想象一个执行排序的函数,直到找到比某些更高的数字$n:

[3, 1, 2, 5, 4, 6] # start here
#^
[3, 1, 2, 5, 4, 6] # look at next number. It's smaller, so we recurse
#^--^
[3, 1, 2, 5, 4, 6] # in recursion: look at next number, replace
#^  ^--^
#|__|
[3, 2, 2, 5, 4, 6] # return new index. It's smaller, so we recurse
#^     ^
#|_____|
[3, 2, 2, 5, 4, 6] # in recursion: look at next number, replace
#^     ^--^
#|_____|
[3, 2, 5, 5, 4, 6] # return new index
#^        ^
#|________|
[3, 2, 5, 5, 4, 6] # It's larger, so we replace and go to new index
#^--------^
[5, 2, 5, 5, 4, 6] # Look at next number. It's smaller, so we recurse
#         ^--^
[5, 2, 5, 5, 4, 6] # In recursion: replace
#         ^  ^--^
#         |__|
[5, 2, 5, 5, 6, 6] # return new index
#         ^     ^
#         |_____|
[5, 2, 5, 5, 6, 6] # It's larger, so we replace. Go to new index
#         ^-----^
[5, 2, 5, 6, 6, 6] # Done!

困难的部分是编写一个执行此操作的函数.由于我们想要编写递归函数,我们必须反思:

• [] - 空数组(没有索引)对自身进行排序
• [6] - 具有单个元素的数组对该元素进行排序
• [4, 6] ? [6, 6] - 如果下一个索引处的元素较大,则将其复制并将新索引放在下一个元素处
• [5, 4, ...] - 如果下一个元素较小,则递归该索引.

示例实现:

sub weird_sort {
  my ($array, $start, $return) = @_;
  $start //= 0;
  my $next = $start + 1;

  while ($next <= $#$array) {
    # check if one is larger
    if ($array->[$start] < $array->[$next]) {
      $array->[$start] = $array->[$next];
      return $next if $return;  # return index to higher levels so that they
                                # can check whether the $next elem is larger.
      $start = $next;
      $next  = $start + 1;
    }
    else {
      $next = weird_sort($array, $next, 1);
    }
  }

  return $next;
}

# called in-place like
weird_sort(\@array);

下一步是删除递归:

sub weird_sort {
  my ($array) = @_;
  my ($start, $next) = (0, 1);

  my @stack;

  while ($next <= $#$array) {
    # check if one is larger
    if ($array->[$start] < $array->[$next]) {
      $array->[$start] = $array->[$next];
      ($start, $next) = @stack ? (pop(@stack), $next) : ($next, $next + 1);
    }
    else {
      push @stack, $start;
      ($start, $next) = ($next, $next + 1);
    }
  }
}

这似乎适用于简单的情况,但我不完全确定这是一个通用的解决方案.