Złożoność obliczeniowa zadania rekrutacyjnego w dwóch wersjach

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Pierwszym pomysłem jest obliczenie iloczynu całej tablicy (złożoność O(n)), a następnie dla każdego elementu tablicy, dzielimy iloczyn przez ten element i dodajemy do nowej tablicy. (złożoność O(n)) Ostatecznie nasza złożoność wynosi O(n).
Problem pojawia się, gdy dodatkowym wymogiem jest brak możliwości użycia dzielenia. Moją propozycją jest wykonanie dzielenia od ręki, to znaczy odejmować liczbę od iloczynu, dopóki nie uzyskamy zera. (w kodzie dzieleniem zajmuje się funkcja process)
Kod w Java:

  static int process(int number, int product) {
    int counter = 0;
    while(product > 0) {
    	product = product - number;
        counter++;
    }
    return counter;
  }
  
  public static void main(String[] args) {
	int[] numbers = new int[]{1, 2, 3, 4, 5};
    int[] results = new int[numbers.length];
    int product = 1;
    
    for(int x : numbers) { 
    	product *= x;
    }
    
   	for(int i = 0; i < numbers.length; i++) {
    	results[i] = process(numbers[i], product);
	}
    
   	for(int i = 0; i < numbers.length; i++) {
    System.out.println(results[i]);
    }
    
    }
}

Jaka jest złożoność obliczeniowa tego kodu?
Moja próba: pierwsza pętla to O(n), metoda process() to O(n), zatem druga pętla to O(n^2). Wizualizacje wyników pomijamy, ostateczna złożoność wynosi O(n^2).

gdy dodatkowym wymogiem jest brak możliwości użycia dzielenia

Obawiam się ze zaimplementowanie dzielenia w taki sposób w jaki to zrobiłeś nie jest poprawnym rozwiązaniem. Chodzi raczej o użycie zupełnie innej metody a nie takie cyrki. W twoim przypadku złożoność to najwyżej jakieś O(n*k) a dla ograniczonych typów liczbowych O(k) jest też ograniczone z góry więc finalnie to nadal jest O(n).

Wracajac do wyjściowego problemu:

• zróbmy tablicę która dla i-tego indeksu zwraca iloczyn wszystkich elementów od początku aż do indeksu i-1
• zróbmy drugą tablicę analogiczną, ale która mnoży od indeksu i+1 to do końca tablicy
• Robienie tych tablic jest trywialne bo tab[i] = tab[i-1]*initialArray[i]

Teraz wynik dla indeksu i to jest tableFront[i] * tableBack[i] i nie ma żadnego dzielenia nigdzie. Złożoność to 3 przejścia przez tablice więc O(3*n) = O(n)

Ja bym zrobił tak (disclamer: nie koduję w Java):

	private static int[] frontMul(int[] t)
	{
	    int[] r = new int[t.length];
	    int mul = 1;
	    for (int i = 0; i < r.length; ++i) {
	         r[i] = mul;
	         mul *= t[i];
	    }
	    return r;
	}
	
	private static int[] backMul(int[] t)
	{
	    int[] r = new int[t.length];
	    int mul = 1;
	    for (int i = r.length - 1; i >=0; --i) {
	         r[i] = mul;
	         mul *= t[i];
	    }
	    return r;
	}
	
	private static int[] solveMullAllButI(int[] t)
	{
	    int[] front = frontMul(t);
	    int[] back = backMul(t);
	    int[] r = new int[t.length];
	
	    for (int i = 0; i < r.length; ++i) {
	         r[i] = front[i] * back[i];
	    }
	    return r;
	}

https://ideone.com/TYiX3H
Wychodzi złożoność liniowa, żadnego dzielenia w żadnej formie.

Czyli dokładnie to co opisał shalom.

def solve(a):
  n=len(a)
  b=[1]*n
  l=r=1
  for i in range(n):
    b[i]*=l
    b[~i]*=r
    l*=a[i]
    r*=a[~i]
  return b

Side note:
jak masz mieć tablicę n liczb, chcesz je mnożyć przez siebie, a potem dzielić to zachodzi jedna z opcji:

• stosujesz liczby całkowite dowolnej precyzji. Wtedy, wyniki pośrednie stają się duże (O(n) bitów), i nie można już powiedzieć że mnożenie jest w czasie stałym.
• stosujesz liczby zmiennoprzecinkowe - wtedy przy jakichkolwiek sensownych wartościach n, dostaniesz szybko inf w wyniku mnożenia, i nici z sensownego wyniku
• stosujesz maszynowe liczby całkowite, które zachowują semantykę przepełnienia (czyli efektywnie arytmetyka modulo 2**32 lub 2**64). Wtedy dzielenie całkowite wypacza jakikolwiek sens, natomiast dzielenie modulo nie jest poprawnie zdefiniowane dla połowy możliwych wartości (tzn liczb parzystych).

Natomiast z tablicą prefiksową (a nie dzieleniem) zadanie staje się zaledwie troszkę bardziej sensowne.

Popularne zadanie. Dla każdego indeksu liczysz iloczyn elementów z lewej strony (jedna tablica) i elementów z prawej strony (druga tablica). Aby uzyskać wynik posiłkujesz się tymi pomocniczymi tablicami - nie ma żadnego dzielenia kosztem większej dodatkowej pamięci (liniowej). Jeżeli w tablicy jest jedno zero, to możesz to zrobić efektywniej. Jeśli jest więcej niż jedno zero - zwracasz tablice zer :)