Mixing
Program complexity
$begingroup$
We have a two-dimensional $n times n$ array containing binary values
binary ($0$ and $1$) where $0$ denotes a black pixel and $1$ a white pixel.
Enter the number of square areas (with the same number of columns and rows), in of which there are as many black pixels as white pixels. For example, found the $2 times 2$ area should have two cells containing white and two pixels containing black pixels. However, a $10 times 10$ area was correctly found should have $50$ white pixels and the same number of black ones. The program should provide for given array, the number of different square areas of any size for which the same number of cells containing 1 as the containing cells were found number $0$.
Calculate the computational complexity of two versions of the program:
not using the partial sum table
using a partial sum table created earlier
The partial sum table stores in the position (k, l) the sum of the analyzed elements
array contained in cells (i, j) for which i<=n, j<=m (in cells located on
left and top of the cell with the address (k, l)). Therefore, to determine the sum of S elements in
In the rectangular area of the table, just refer to the four values from the sum table
partial parts according to the formula: S = D + A-B-C
computational-complexity
edited Jan 7 at 19:00
David G. Stork
10.9k31432
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
$endgroup$
|
show 1 more comment
$begingroup$
We have a two-dimensional $n times n$ array containing binary values
binary ($0$ and $1$) where $0$ denotes a black pixel and $1$ a white pixel.
Enter the number of square areas (with the same number of columns and rows), in of which there are as many black pixels as white pixels. For example, found the $2 times 2$ area should have two cells containing white and two pixels containing black pixels. However, a $10 times 10$ area was correctly found should have $50$ white pixels and the same number of black ones. The program should provide for given array, the number of different square areas of any size for which the same number of cells containing 1 as the containing cells were found number $0$.
Calculate the computational complexity of two versions of the program:
not using the partial sum table
using a partial sum table created earlier
The partial sum table stores in the position (k, l) the sum of the analyzed elements
array contained in cells (i, j) for which i<=n, j<=m (in cells located on
left and top of the cell with the address (k, l)). Therefore, to determine the sum of S elements in
In the rectangular area of the table, just refer to the four values from the sum table
partial parts according to the formula: S = D + A-B-C
computational-complexity
edited Jan 7 at 19:00
David G. Stork
10.9k31432
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
$endgroup$
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11
|
show 1 more comment
$begingroup$
We have a two-dimensional $n times n$ array containing binary values
binary ($0$ and $1$) where $0$ denotes a black pixel and $1$ a white pixel.
Enter the number of square areas (with the same number of columns and rows), in of which there are as many black pixels as white pixels. For example, found the $2 times 2$ area should have two cells containing white and two pixels containing black pixels. However, a $10 times 10$ area was correctly found should have $50$ white pixels and the same number of black ones. The program should provide for given array, the number of different square areas of any size for which the same number of cells containing 1 as the containing cells were found number $0$.
Calculate the computational complexity of two versions of the program:
not using the partial sum table
using a partial sum table created earlier
The partial sum table stores in the position (k, l) the sum of the analyzed elements
array contained in cells (i, j) for which i<=n, j<=m (in cells located on
left and top of the cell with the address (k, l)). Therefore, to determine the sum of S elements in
In the rectangular area of the table, just refer to the four values from the sum table
partial parts according to the formula: S = D + A-B-C
computational-complexity
edited Jan 7 at 19:00
David G. Stork
10.9k31432
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
$endgroup$
We have a two-dimensional $n times n$ array containing binary values
binary ($0$ and $1$) where $0$ denotes a black pixel and $1$ a white pixel.
Enter the number of square areas (with the same number of columns and rows), in of which there are as many black pixels as white pixels. For example, found the $2 times 2$ area should have two cells containing white and two pixels containing black pixels. However, a $10 times 10$ area was correctly found should have $50$ white pixels and the same number of black ones. The program should provide for given array, the number of different square areas of any size for which the same number of cells containing 1 as the containing cells were found number $0$.
Calculate the computational complexity of two versions of the program:
not using the partial sum table
using a partial sum table created earlier
The partial sum table stores in the position (k, l) the sum of the analyzed elements
array contained in cells (i, j) for which i<=n, j<=m (in cells located on
left and top of the cell with the address (k, l)). Therefore, to determine the sum of S elements in
In the rectangular area of the table, just refer to the four values from the sum table
partial parts according to the formula: S = D + A-B-C
computational-complexity
computational-complexity
edited Jan 7 at 19:00
David G. Stork
10.9k31432
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
edited Jan 7 at 19:00
David G. Stork
10.9k31432
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
edited Jan 7 at 19:00
David G. Stork
10.9k31432
edited Jan 7 at 19:00
David G. Stork
10.9k31432
edited Jan 7 at 19:00
David G. Stork
10.9k31432
10.9k31432
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
asked Jan 7 at 18:57
DzaroslawDzaroslaw
1
1
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11
|
show 1 more comment
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11
|
show 1 more comment
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3065354%2fprogram-complexity%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3065354%2fprogram-complexity%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
What's the problem? The simple program is linear in the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:01
$begingroup$
I do not know how to write it from the mathematical side to set it.
$endgroup$
– Dzaroslaw
Jan 7 at 19:05
$begingroup$
A linear function is written ${cal O}(n)$, where $n$ is the number of pixels queried.
$endgroup$
– David G. Stork
Jan 7 at 19:06
$begingroup$
I am not talking about the result itself but about the way in which it is calculated
$endgroup$
– Dzaroslaw
Jan 7 at 19:09
$begingroup$
I urge you to read any basic text or website on computational complexity. I cannot imagine a simpler problem in that domain than this.
$endgroup$
– David G. Stork
Jan 7 at 19:11