Dados os n
números em uma matriz (você não pode assumir que sejam números inteiros), gostaria de calcular o produto de todos os subconjuntos de tamanho n-1
.
Você pode fazer isso multiplicando todos os números e depois dividindo cada um por vez, desde que nenhum deles seja zero. No entanto, com que rapidez você pode fazer isso sem divisão?
Se você não permite a divisão, qual é o número mínimo de operações aritméticas (por exemplo, multiplicação e adição) necessárias para calcular o produto de todos os subconjuntos de tamanho n-1?
Claramente você pode fazê-lo em (n-1)*n
multiplicações.
Para esclarecer, a saída é de n
produtos diferentes e as únicas operações além da leitura e gravação na memória permitidas são multiplicação, adição e subtração.
Exemplo
Se a entrada tem três números 2,3,5
, então a saída é de três números 15 = 3*5
, 10 = 2*5
e 6 = 2*3
.
Critério de vitória
As respostas devem fornecer uma fórmula exata para o número de operações aritméticas que seu código usará em termos de n
. Para simplificar a vida, apenas conectarei n = 1000
sua fórmula para avaliar sua pontuação. Quanto menor, melhor.
Se for muito difícil produzir uma fórmula exata para o seu código, você pode executá-la n = 1000
e contar as operações aritméticas no código. Uma fórmula exata seria melhor no entanto.
Você deve adicionar sua pontuação n=1000
à sua resposta para facilitar a comparação.
fonte
+
nos índices, contam? Se for esse o caso, a indexação de array também conta? (já que, afinal, é açúcar sintático para adição e desreferenciação).(n-1)*n
multiplicações. Você quer dizer(n-2)*n
, certo?Respostas:
Python, 3 (n-2) operações, score = 2994
As matrizes
left
eright
contêm os produtos acumulados da matriz da esquerda e da direita, respectivamente.EDIT: Prova de que 3 (n-2) é o número ideal de operações necessárias para n> = 2, se usarmos apenas a multiplicação.
Faremos isso por indução; pelo algoritmo acima, apenas temos que provar que para n> = 2, 3 (n-2) é um limite inferior ao número de multiplicações necessárias.
Para n = 2, precisamos de pelo menos 0 = 3 (2-2) multiplicações, portanto o resultado é trivial.
Seja n> 2 e suponha que para n - 1 elementos, precisamos de pelo menos 3 (n-3) multiplicações. Considere uma solução para n elementos com k multiplicações. Agora, removemos o último desses elementos como se fosse 1 e simplificamos todas as multiplicações diretamente por ele. Também removemos a multiplicação que leva ao produto de todos os outros elementos, pois esse não é necessário, pois nunca pode ser usado como um valor intermediário para obter o produto de n-2 dos outros elementos, pois a divisão não é permitida. Isso nos deixa com l multiplicações e uma solução para n - 1 elementos.
Pela hipótese de indução, temos l> = 3 (n-3).
Agora, vamos dar uma olhada em quantas multiplicações foram removidas. Um deles foi o que levou ao produto de todos os elementos, exceto o último. Além disso, o último elemento foi usado diretamente em pelo menos duas multiplicações: se foi usado em apenas uma, então foi usado quando multiplicado por um resultado intermediário que consistia em algum produto dos outros elementos; digamos, sem perda de generalidade, esse resultado intermediário incluiu o primeiro elemento no produto. Portanto, não há como obter o produto de todos os elementos, exceto o primeiro, pois todo produto que contém o último elemento é o último elemento ou contém o primeiro elemento.
Temos, portanto, k> = l + 3> = 3 (n-2), comprovando o teorema reivindicado.
fonte
f l = zipWith (*) (scanl (*) 1 l) (scanr (*) 1 $ tail l)
.Haskell , pontuação 2994
Experimente online!
Digamos que recebemos a lista
[a,b,c,d,e,f,g,h]
. Primeiro, agrupamos em pares[[a,b],[c,d],[e,f],[g,h]]
. Em seguida, recuamos na listapairs
de tamanho médio de seus produtos para obtersubresults
Se pegarmos o primeiro elemento
(c*d)*(e*f)*(g*h)
e multiplicá-lo porb
ea
respectivamente, obteremos o produto de todos, excetoa
todos e menosb
. Fazendo isso para cada par e resultado recursivo com esse par faltando, obtemos o resultado final. O caso de comprimento ímpar é tratado especialmente por ter o elemento ímpar passado sem par para a etapa recursiva, e o produto dos elementos restantes retornados é o produto sem ele.O número de multiplicações
t(n)
én/2
para o produto de emparelhamento,t(n/2)
para a chamada recursiva e outron
para os produtos com elementos individuais. Isso dát(n) = 1.5 * n + t(n/2)
para estranhon
. Usar uma contagem mais precisa para ímparn
e ignorar a multiplicação1
para o caso base fornece pontuação2997
paran=1000
.fonte
products_but_one'
possa evitar isso retornando algo do tamanho correto.1
que é livre para multiplicar. Acho que o preenchimento 1 não afetou as coisas, mas limpei meu algoritmo para não usá-las.float
.Haskell , pontuação 9974
Experimente online!
Uma estratégia de dividir e conquistar, muito reminiscente do tipo de mesclagem. Não faz nenhuma indexação.
A função
partition
divide a lista em metades o mais igual possível, colocando elementos alternados em lados opostos da partição. Mesclamos recursivamente os resultados(p,r)
para cada uma das metades, comr
a lista de produtos com uma falta ep
o produto geral.Para a saída da lista completa, o elemento ausente deve estar em uma das metades. O produto com esse elemento ausente é um produto que falta na metade, multiplicado pelo produto completo para a outra metade. Portanto, multiplicamos cada produto por um faltando pelo produto completo da outra metade e fazemos uma lista dos resultados, como
map(*p1)r2 ++ map(*p2)r1)
. Isso levan
multiplicações, onden
está o comprimento. Também precisamos criar um novo produto completop1*p2
para uso futuro, custando mais 1 multiplicação.Isto dá a recursão geral para o número de operações
t(n)
comn
mesmo:t(n) = n + 1 + 2 * t(n/2)
. O ímpar é semelhante, mas um dos sublistas é1
maior. Fazendo a recursão, obtemosn*(log_2(n) + 1)
multiplicações, embora a distinção ímpar / par afete esse valor exato. Os valores atét(3)
são aprimorados, não multiplicando1
, definindo uma variante(%)
desses(*)
atalhos the_*1
ou1*_
cases.Isso dá
9975
multiplicações paran=1000
. Acredito que a preguiça de Haskell significa que o produto geral não utilizado na camada externa não é calculado9974
; se estiver enganado, posso omitir explicitamente.fonte
n = 1000
e contar as operações aritméticas no código.9974
e não as9975
multiplicaçõesn = 1000
(no caso de calcular o produto geral na camada externa). Você incluiu um1
na entrada usada para testá-lo?trace
a partirDebug.Trace
com um catch-all| trace "call!" False = undefined
guarda, eu acho. Mas isso é feitounsafePerformIO
sob o capô, então não é realmente uma grande melhoria.Haskell , pontuação 2994
Experimente online!
Como funciona
Esta é uma versão limpa do algoritmo do xnor que lida com o caso ímpar de maneira mais direta (editar: parece que o xnor o limpou da mesma maneira):
[a, b, c, d, e, f, g] ↦
[a, bc, de, fg] ↦
[(bc) (de) (fg), a (de) (fg), a (bc) ( fg), a (bc) (de)] por recursão ↦
[(bc) (de) (fg), a (de) (fg) c, a (de) (fg) b, a (bc) (fg) e, a (bc) (fg) d, a (bc) (de) g, a (bc) (de) f]
[a, b, c, d, e, f, g, h] ↦
[ab, cd, ef, gh] ↦
[(cd) (ef) (gh), (ab) (ef) (gh), ( ab) (cd) (gh), (ab) (cd) (ef)] por recursão ↦
[(cd) (ef) (gh) b, (cd) (ef) (gh) a, (ab) (ef) (gh) d, (ab) (ef) (gh) c, (ab) (cd) (gh) f, (ab) (cd) (gh) e, (ab) (cd) (ef) h, (ABCDEFG].
fonte
O (n log n) operações, pontuação = 9974
Funciona com uma árvore binária.
Python
Isso também requer operações de adição de lista e alguma aritmética em números que não são os valores de entrada; não tenho certeza se isso conta. A
mul
função existe para salvar n operações para o caso base, para evitar desperdiçá-las multiplicando por 1. Em qualquer caso, são operações O (n log n). A fórmula é exacto, se somente uma contagem de operações aritméticas sobre os números de entrada, comj = floor(log_2(n))
:j * (2^(j + 1) - n) + (j + 1) * (2 * n - 2^(j + 1)) - 2
.Agradecemos ao @xnor por salvar uma operação com a idéia de não computar o produto externo!
A última parte é produzir os produtos na ordem do termo que falta.
fonte
n = 1000
e contar as operações aritméticas no código.p[i] = p[i + i] * p[i + i+1]
não é contadon log2 n + n
operações (que é O (nlogn) btwp[i] = p[i + i] * p[i + i + 1]
devem ser salvas pela otimização da multiplicação. Eu poderia ter contado um número demais, no entanto.O ((n-2) * n) = O (n 2 ): Solução trivial
Esta é apenas a solução trivial que multiplica juntos cada um dos subconjuntos:
Python
Observe que isso também requer
n
operações de adição de lista; não tenho certeza se isso conta. Se isso não for permitido,product(array[:index] + array[index + 1:])
poderá ser substituído porproduct(array[:index]) * product(array[index + 1:])
, que altera a fórmula paraO((n-1)*n)
.fonte
product
funcionaisO(n)
? um para cada elemento na matriz (althought isso pode facilmente ser alterados paraO(n-1)
)Python, 7540
Uma estratégia de mesclagem tripartida. Eu acho que posso fazer ainda melhor do que isso, com uma fusão ainda grande. É O (n log n).
EDIT: Corrigido um miscount.
A função relevante é
missing_products
, que fornece ao produto geral e a todos os que faltam um elemento.fonte
tri_merge
? Além disso, você pode substituir o2 * split_size + ...
emtri_partition
comsplit_size + split_size + ...
.dc, pontuação 2994
Estou assumindo que a comparação inteira
z1=
(que termina a recursão quando atingimos o último valor) é gratuita. Isso é equivalente aos gostos deforeach
outros idiomas.Manifestações
Uma demonstração com entradas grandes e pequenas:
fonte
C ++, pontuação: 5990, O ([2NlogN] / 3)
Esta implementação usa uma tabela de pesquisa de árvore binária. Minha primeira implementação foi O (NlogN), mas uma otimização de última hora, que procura o produto de todos os elementos da matriz menos um par, + 2 multiplicações salvas no dia. Acho que isso ainda pode ser otimizado um pouco mais, talvez outros 16% ...
Deixei alguns traços de depuração, apenas porque é mais fácil excluí-los do que reescrevê-los :)
[Editar] a complexidade real é medida em O ([2NlogN] / 3) para 100. Na verdade, é um pouco pior que O (NlogN) para pequenos conjuntos, mas tende para O ([NlogN] / 2) à medida que a matriz cresce. O muito grande (0.57.NlogN) para um conjunto de 1 milhão de elementos.
Estou adicionando o algoritmo de @ nore, para ser completo. É muito bom e é o mais rápido.
fonte