Как найти количество нулей в матрице

Without storing any external information, no, you can’t do any better than Θ(N²). The rationale is simple – if you don’t look at all N² locations in the matrix, then you can’t guarantee that you’ve found all of the zeros and might end up giving the wrong answer back. For example, if I know that you look at fewer than N² locations, then I can run your algorithm on a matrix and see how many zeros you report. I could then look at the locations that you didn’t access, replace them all with zeros, and run your algorithm again. Since your algorithm doesn’t look at those locations, it can’t know that they have zeros in them, and so at least one of the two runs of the algorithm would give back the wrong answer.

More generally, when designing algorithms to process data, a good way to see if you can do better than certain runtimes is to use this sort of “adversarial analysis.” Ask yourself the question: if I run faster than some time O(f(n)), could an adversary manipulate the data in ways that change the answer but I wouldn’t be able to detect? This is the sort of analysis that, along with some more clever math, proves that comparison-based sorting algorithms cannot do any better than Ω(n log n) in the average case.

If the matrix has some other properties to it (for example, if it’s sorted), then you might be able to do a better job than running in O(N²). As an example, suppose that you know that all rows of the matrix are sorted. Then you can easily do a binary search on each row to determine how many zeros it contains, which takes O(N log N) time and is faster.

Depending on the parameters of your setup, you might be able to get the algorithm to run faster if you assume that you’re allowed to scan in parallel. For example, if your machine has K processors on it that can be dedicated to the task of scanning the matrix, then you could split the matrix into K roughly evenly-sized groups, have each processor count the number of zeros in the group, then sum the results of these computations up. This ends up giving you a runtime of Θ(N² / K), since the runtime is split across multiple cores.

#include <stdio.h>
#include <conio.h>
main()
{
int s[3][3];
int i,j,o,a,b,c;
o=0;a=0;b=0;c=0;
printf("Vvedite matricu 3x3n");
for(i=0;i<=2;i=i+1){
  for(j=0;j<=2;j=j+1){
                      scanf("%d", &s);
                     }}
for(i=0;i<=2;i=i+1){
 for(j=0;j<=2;j=j+1){
                     if(s[i][j]==0){o=o+1;}
                     }}
                     printf("Vsego v matrice nulei: %dn", o);
for(i=0;i<=0;i++){
 for(j=0;j<=2;j=j+1){
                     if(s[i][j]==0){a=a+1;}
                     }}
                     printf("V pervoy stroke nulei: %dn", a);
for(i=1;i<=1;i++){
 for(j=0;j<=2;j=j+1){
                     if(s[i][j]==0){b=b+1;}
                     }}
                     printf("V vtoroy stroke nulei: %dn", b);
for(i=2;i<=2;i++){
 for(j=0;j<=2;j=j+1){
                     if(s[i][j]==0){c=c+1;}
                     }}
                     printf("V tretey stroke nulei: %dn", c);
                     getch();//PAUSE                                          
 
}

Вопрос:

У меня есть матрица NxM, например, с именем A. После некоторых процессов я хочу подсчитать нулевые элементы.
Как я могу сделать это в одном коде строки? Я попробовал A==0, который возвращает 2D-матрицу.

Ответ №1

A = [1, 3, 1;
0, 0, 2;
0, 2, 1];
nnz(A==0)  %// returns 3, i.e. the number of zeros of A (the amount of true in A==0)

Ответ №2

sum(~A(:))

sum(A(:)==0)

Ответ №3

histc(A(:), 0)

Ответ №4

    % Random Matrix
M = [1 0 4 8 0 6;
0 0 7 4 8 0;
8 7 4 0 6 0];

n = size(M,1); % Number of lines of M
p = size(M,2); % Number of columns of M

nbrOfZeros = 0; % counter

for i=1:n
for j=1:p
if M(i,j) == 0
nbrOfZeros = nbrOfZeros + 1;
end
end
end

nbrOfZeros